Chromatic polynomial P(G,k): number of proper k-colorings. P(K_n,k)=k^{(n)} (falling factorial). P(tree,k)=k(k-1)^{n-1}. P(C_n,k)=(k-1)^n+(-1)^n(k-1). The chromatic number χ(G) is the smallest k with P(G,k)>0.
How to Use
Select graph:
- P(G,k): Polynomial formula
- Evaluate: P at specific k
- Roots: Chromatic roots
Deletion-Contraction
P(G,k) = P(G-e,k) - P(G/e,k). Delete edge e: P(G-e). Contract edge e: P(G/e). Recursion reduces to edgeless graphs where P(E_n,k)=k^n. This gives both the formula and a computation method.
Properties
P(G,k) is always a polynomial of degree n (vertices). Leading coefficient is 1. Coefficient of k^{n-1} is -|E|. The coefficients alternate in sign. Chromatic roots can be complex.
Step-by-Step Instructions
- 1Select graph.
- 2Compute P(G,k).
- 3Evaluate at k.
- 4Find χ(G).
- 5Study roots.