Chromatic Polynomial Examples

Graph Theory · Axiom Academy

EXAMPLE Chromatic Polynomial Examples Master computing P(G,k) using deletion-contraction and recognize key patterns Excellent work! You've mastered chromatic polynomial computation. Here's what we learned: Deletion-Contraction: The fundamental recurrence P(G,k) = P(G-e,k) - P(G/e,k) systematically reduces any graph to base cases. Base Cases: Complete graphs K n give k(k-1)···(k-n+1), empty graphs give k n , and paths/cycles have closed forms. Chromatic Number: χ(G) is the smallest positive integer k where P(G,k) > 0, found by testing small values. Verification: Direct counting validates polynomial results for small k by enumerating proper colorings systematically. Special Cases: Recognizing standard families (paths, cycles, complete graphs) speeds up computation dramatically. Polynomial Properties: P(G,k) is always a polynomial of degree n with leading coefficient 1, alternating signs, and integer roots. The chromatic polynomial encodes deep structural information about a graph's coloring behavior across all possible numbers of colors!

This is the written version of the interactive lesson above. See the full Graph Theory course.