Chromatic Polynomial

Graph Theory · Axiom Academy

Understanding the polynomial that counts proper colorings of a graph The chromatic polynomial P(G, k) is defined as the number of proper k-colorings of graph G. A proper coloring assigns colors to vertices so that adjacent vertices have different colors. 2. Why It's Actually a Polynomial At first glance, it's surprising that a counting function yields a polynomial. The key insight comes from the deletion-contraction recurrence relation, which builds P(G, k) systematically. Starting from an empty graph (all vertices, no edges), each vertex can be colored independently in k ways. Adding edges introduces constraints that reduce the count in a structured way. 3. Deletion-Contraction Formula For any edge e in graph G, the chromatic polynomial satisfies: Where G - e is the graph with edge e removed, and G / e is the graph with edge e contracted (merging its endpoints into one vertex). 4. Example: Complete Graph K_n In a complete graph K_n, every pair of vertices is connected. Therefore, all n vertices must receive different colors. This is a falling factorial: we have k choices for the first vertex, k-1 for the second, and so on, giving us k(k-1)(k-2)...(k-n+1). 5. Example: Trees with n Vertices For any tree T with n vertices (a connected acyclic graph), the chromatic polynomial has a remarkably simple form. We can color the root in k ways, then each subsequent vertex (moving away from the root) in k-1 ways, avoiding only its parent's color.

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