Chromatic polynomials, list coloring, and beyond four colors
Count every coloring, give each vertex its own palette, or move the map onto a doughnut, and the four color story changes.
Load a preset or use Add Vertices and Add Edges to build a small graph, and watch its chromatic polynomial update. Notice how each new edge cuts the number of colorings.
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 |
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. The deletion-contraction algorithm computes P(G, k) recursively: delete an edge or contract it, and combine the results.
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.
Pick a scenario, click a vertex, and give it a color from its own list. The easier lists can be solved; in the Hard case, 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.
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?
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.
Switch between the plane, torus, Klein bottle, and double torus, and compare each surface's chromatic number with the Heawood formula.
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.
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.
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.
The four color theorem is uniquely difficult: the plane is the only surface where the Heawood formula's value could not be proved by Heawood's argument -- it took a century and a computer.
Spot a mistake or have an idea?