Chromatic number, the four color theorem, and applications
Graph coloring assigns labels (called "colors") to vertices so that no two adjacent vertices share the same color. This seemingly simple concept has profound applications in scheduling, map making, and computer science!
In this section, you'll discover the chromatic number, learn coloring algorithms, explore the famous Four Color Theorem, and see how graph coloring solves real scheduling problems.
The chromatic number χ(G) is the minimum number of colors needed to color a graph so no adjacent vertices share a color. Select a color and click vertices to color them!
Click a vertex to color it with the selected color
The greedy algorithm colors vertices in order, always picking the smallest available color. Watch how different orderings can produce different results!
Note: Greedy doesn't always find the optimal coloring! Different orderings can give different results. Try shuffling and running again!
The Four Color Theorem states that any map can be colored with at most 4 colors such that no adjacent regions share a color. Try coloring this map!
Click a region to color it. Hover to see adjacent regions highlighted.
First conjectured in 1852, the Four Color Theorem was proven in 1976 by Appel and Haken using computer-assisted proof — the first major theorem to be proven this way!
The theorem states: Any planar graph can be colored with at most 4 colors such that no two adjacent vertices share a color. This applies directly to map coloring since maps are planar graphs.
Graph coloring solves real scheduling problems! Here, exams are vertices, and edges connect exams with shared students (can't be at the same time). Colors represent time slots.
Click an exam to select it, then choose a time slot below
1. Chromatic Number: The chromatic number χ(G) is the minimum number of colors needed for a proper vertex coloring. Finding χ(G) is NP-hard in general, but some graphs have known values: complete Kn has χ = n, bipartite graphs have χ = 2.
2. Greedy Coloring: Process vertices in order, assigning the smallest available color. It's fast (O(V + E)) but doesn't always find the optimal coloring—the result depends on vertex ordering.
3. Four Color Theorem: Any planar graph (and thus any map) can be colored with at most 4 colors. This was proven in 1976 using computer assistance, making it one of the first major computer-assisted proofs.
4. Applications: Graph coloring models many real problems: exam scheduling (conflicts = edges, colors = time slots), register allocation in compilers, frequency assignment in wireless networks, and even Sudoku puzzles!
Next Up: In the next section, you'll learn about planar graphs — graphs that can be drawn without edge crossings, Euler's formula, and Kuratowski's theorem!