How to find the chromatic number of a graph and prove it with graph coloring?

**Chromatic numbers of basic graphs:** - $\chi(K_n) = n$ (all $n$ vertices pairwise adjacent) - $\chi(K_{m,n}) = 2$ (bipartite, so 2-colorable) - $\chi(C_n) = 2$ if $n$ even, $\chi(C_n) = 3$ if $n$ odd **Brooks' Theorem:** For a connected graph $G$ that is not complete or an odd cycle, $$\chi(G) \leq \Delta(G)$$ where $\Delta(G)$ is the maximum degree. **Greedy Coloring Algorithm:** 1. Order vertices $v_1, v_2, \ldots, v_n$. 2. For each vertex in order, assign the smallest color not used by any already-colored neighbor. 3. The greedy algorithm uses at most $\Delta(G) + 1$ colors, but the order matters. **Four Color Theorem:** Every planar graph is 4-colorable. This was the first major theorem proved by computer (Appel and Haken, 1976). Equivalent to: no planar graph requires 5 colors. **Petersen Graph:** $\chi(P) = 3$. It is not bipartite (has odd cycles) but can be colored with 3 colors. It's 3-regular, so by Brooks' theorem $\chi \leq 3$, and $\chi > 2$ since it has odd cycles. **Applications:** - **Exam scheduling:** Courses = vertices, conflicts = edges, colors = time slots - **Register allocation:** Variables = vertices, interference = edges, colors = CPU registers - **Map coloring:** Countries = vertices, borders = edges, colors = colors on map