Graph Coloring assigns colors to vertices so no two adjacent vertices share a color. The minimum number of colors needed is the chromatic number χ(G).
Brooks' theorem: For any connected graph that is not a complete graph or odd cycle, χ(G) ≤ Δ (maximum degree). Four-color theorem (Appel & Haken, 1976): Every planar graph satisfies χ(G) ≤ 4. Chromatic polynomial χ(G,k) counts the number of proper k-colorings. For a path Pₙ: χ = k(k−1)ⁿ⁻¹. For a cycle Cₙ: χ = (k−1)ⁿ + (−1)ⁿ(k−1).