Coloring Maps and Beyond
The graph coloring problem has its roots in cartography: can you color a map so that no two neighbouring countries share the same color? In 1852, Francis Guthrie conjectured that four colors always suffice for any planar map — a claim that took 124 years and a computer to prove. But graph coloring extends far beyond maps into scheduling, wireless frequency allocation, compiler optimization, and combinatorial puzzles like Sudoku.
Greedy Coloring Algorithm
The simplest approach is greedy: process vertices one by one and assign each the smallest color not already used by its neighbours. This runs in O(V + E) time and guarantees at most Δ+1 colors, where Δ is the maximum vertex degree. However, the result depends heavily on vertex ordering — a bad order can use far more colors than necessary, while an optimal order achieves the chromatic number.
The Chromatic Number
The chromatic number χ(G) is the minimum number of colors needed for a proper coloring. Computing it exactly is NP-hard, meaning no known polynomial-time algorithm exists for general graphs. Special cases are easier: bipartite graphs need 2 colors, trees need 2, complete graphs on n vertices need n, and planar graphs need at most 4 (by the four color theorem). Brooks' theorem sharpens the greedy bound to Δ for graphs that aren't complete or odd cycles.
From Theory to Silicon
One of the most important practical applications of graph coloring is register allocation in compilers. Variables that are simultaneously alive in a program form an interference graph; coloring this graph with k colors corresponds to assigning k CPU registers. When k colors aren't enough, the compiler must 'spill' variables to memory — a costly operation. Better coloring heuristics directly translate to faster compiled code.