Concept
Coloring nodes so neighbors differ — from maps to compilers to scheduling.
Understand it in one breath
"How few colors do you need so adjacent regions never share a color?" A student's 1852 question led, 124 years later, to the Four Color Theorem — one of the first major theorems whose proof depended on computer checking. School timetabling, radio-frequency allocation, and compiler register allocation can all be modeled as graph coloring.
At a glance
Graph type | χ(G) | Real-world application |
|---|---|---|
Planar map (Four Color Theorem) | ≤ 4 | Political maps, GIS |
Bipartite graph (no odd cycle) | 2 | Student-course matching |
n-clique (Kₙ) | n | Complete graph |
Odd cycle | 3 | Timetable conflicts |
Petersen graph | 3 | A standard textbook example |
Tree | 2 | Hierarchical structures |
χ(G) is the chromatic number of G: the minimum number of colors needed so adjacent vertices differ. Computing it in general is NP-complete.
Key formula
Key moments
The four-color conjecture
Francis Guthrie conjectured that four colors would suffice for every planar map after coloring a map of English counties.
The Four Color Theorem is proved by computer
Kenneth Appel and Wolfgang Haken completed the first famous computer-assisted proof of a major theorem.
Graph coloring as an NP-complete problem
Complexity theory established that deciding whether a graph can be colored with three colors is NP-complete, exposing the difficulty of graph coloring in general.
Modern applications
Compiler register allocation, timetable scheduling, frequency assignment, GIS maps, and collision avoidance in graphics workloads.
Beyond MathVoyage
Loading…