Chromatic polynomials, list coloring, and beyond four colors
The four color theorem sits at the intersection of many mathematical threads. Chromatic polynomials count the exact number of colorings. List coloring asks what happens when each vertex has its own palette. And on surfaces beyond the plane, the story changes completely.
The chromatic polynomial P(G, k) counts exactly how many proper k-colorings a graph G has. Build a small graph below and watch the polynomial update in real time. The deletion-contraction algorithm computes P(G, k) recursively: delete an edge or contract it, and combine the results.
Click two vertices to add an edge between them.
P(G, k) = k^4 - 6k^3 + 11k^2 - 6k
| k | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| P(G, k) | 0 | 0 | 0 | 24 | 120 |
Key insight: The chromatic polynomial P(G, k) counts exactly how many proper k-colorings a graph has. The four color theorem says P(G, 4) > 0 for every planar graph. Deletion-contraction lets us compute P(G, k) recursively.
In list coloring, each vertex has its own list of allowed colors. Can you always find a proper coloring using only the colors in each vertex's list? Try the scenarios below -- especially the hard one, where carefully chosen 2-color lists make it impossible.
Each vertex has all 5 colors available, so list coloring reduces to ordinary coloring. This graph is bipartite, so even 2 colors would suffice.
Click a vertex to select it, then choose a color from its list on the right. Small dots show each vertex's allowed colors.
Click a vertex to see its available colors.
Key insight: In list coloring, each vertex has its own list of allowed colors. Thomassen proved every planar graph is 5-list-colorable, but some planar graphs are NOT 4-list-colorable -- list coloring is strictly harder than ordinary coloring.
What happens when we color maps on surfaces other than the plane? On a torus (a doughnut), 7 colors are needed. The Heawood formula gives the chromatic number for every surface except the Klein bottle -- and for the plane, its value of 4 is correct but proving it required the four color theorem.
Surface properties
Genus: 0 | Orientable
Chromatic number
4
Heawood formula
H(g) = floor( (7 + sqrt(48g + 1)) / 2 )
For genus 0, the formula gives 4 but the four color theorem requires a separate (much harder) proof.
The plane and sphere are equivalent for coloring purposes. The four color theorem (proved by Appel and Haken, 1976) states that 4 colors suffice. The Heawood formula does not apply directly -- it gives an upper bound of 4 but does not prove it.
Key insight: On a torus, 7 colors are needed and sufficient (Heawood conjecture, proved by Ringel and Youngs). The four color theorem is actually the hardest case -- the plane is the one surface where Heawood's argument cannot prove the bound, so a separate proof was needed.