gen-define-graph-coloring-counts-and-give-one-short-worked-examp-c8ec

Define graph coloring counts and give one short worked example.

# Graph Coloring Counts The **chromatic polynomial** P(G, k) counts the number of proper k-colorings of a graph G, where a proper coloring assigns colors to vertices such that no two adjacent vertices share the same color. ## Key Properties - P(G, k) is a polynomial in k - For k ≥ χ(G) (the chromatic number), P(G, k) gives the count of valid colorings - Calculated using deletion-contraction or other methods ## Worked Example **Graph:** A triangle (3-cycle: K₃) ``` 1 — 2 \ / 3 ``` **Find P(K₃, k):** - **Vertex 1:** k color choices - **Vertex 2:** (k-1) choices (can't use vertex 1's color) - **Vertex 3:** (k-2) choices (can't use colors from vertices 1 or 2) **Result:** P(K₃, k) = k(k-1)(k-2) **Specific values:** - P(K₃, 2) = 2(1)(0) = **0** colorings (impossible with 2 colors) - P(K₃, 3) = 3(2)(1) = **6** colorings (each of 3! color permutations) - P(K₃, 4) = 4(3)(2) = **24** colorings