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. The minimum number of colors needed for a proper coloring is called the chromatic number of the graph.
Finding the chromatic number is NP-hard in general, but greedy algorithms provide fast approximations. The celebrated Four Color Theorem guarantees that every planar graph can be properly colored with at most four colors. Graph coloring also models practical problems such as exam scheduling and register allocation.
Select a color from the palette and click vertices to color them. Try to achieve a proper coloring using the minimum number of colors. Switch between preset graphs with known chromatic numbers to test your intuition.
Click a vertex to color it with the selected color
Key insight: Complete graphs Kn require exactly n colors, bipartite graphs need only 2, and odd cycles need 3. The chromatic number captures the essential "conflict density" of a graph.
The greedy algorithm processes vertices in a fixed order, assigning each the smallest color not used by its already-colored neighbors. Shuffle the vertex ordering and run the algorithm again to see how different orderings produce different results.
Key insight: Greedy coloring runs in O(V + E) time but does not always achieve the optimal chromatic number. The result depends entirely on the vertex ordering, and some orderings may use far more colors than necessary.
The Four Color Theorem states that any map can be colored with at most four colors so that no two adjacent regions share a color. Select a color and click regions to color this map. Hover over a region to highlight its neighbors.
Click a region to color it. Hover to see adjacent regions highlighted.
Key insight: 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 require computational verification.
Graph coloring models real scheduling problems. Here, exams are vertices and edges connect exams with shared students. Colors represent time slots. Click an exam to select it, then assign a time slot, or let the greedy algorithm schedule automatically.
Click an exam to select it, then choose a time slot below
Key insight: Graph coloring appears in register allocation (variables that overlap in lifetime cannot share a register), frequency assignment (adjacent transmitters need different frequencies), and even Sudoku puzzles.