Graph coloring assigns colors to graph vertices so that adjacent vertices have different colors. The chromatic number χ(G) is the minimum number of colors needed.
It looks like a puzzle problem; it's also the abstract structure behind register allocation, scheduling, frequency assignment, and timetabling.
Given an undirected graph G = (V, E), color each vertex such that no two adjacent vertices share a color. Minimize the number of colors used.
Two colors suffice (alternate). χ = 2.
All pairs adjacent. χ = n.
Two-colorable (one color per side). χ = 2.
A graph is bipartite iff it has no odd cycles.
By the Four Color Theorem (1976): every planar graph is 4-colorable.
The proof was the first major theorem proven by computer.
"Is G k-colorable?"
Computing χ(G) is NP-hard.
Approximating χ(G) is also hard. There's no polynomial algorithm with reasonable approximation ratio under standard complexity assumptions.
In practice: heuristics dominate.
Order vertices; color each with smallest available color.
Quality depends on order:
Greedy is fast but can use much more than χ colors.
At each step, color the vertex with most distinct neighbor colors. Tie-break by degree.
Often produces near-optimal colorings.
Try colors; backtrack on conflict. Optimal but exponential.
For small graphs (~30 vertices), works fine.
Start with a coloring; try recoloring conflicting vertices.
Tabu search and simulated annealing variants are common.
Encode as ILP; solve with commercial solvers (Gurobi, CPLEX).
Practical for moderate graphs.
Color edges so adjacent edges (sharing a vertex) differ.
Vizing's theorem: χ'(G) is Δ or Δ+1, where Δ is max degree.
Edge coloring is also NP-hard but has tighter bounds.
Each vertex has a list of allowed colors. Find proper coloring respecting lists.
Choosability ch(G) ≥ χ(G).
Each vertex represents an interval; coloring the interval graph.
Equivalent to scheduling on machines.
Color both vertices and edges; adjacent or incident things differ.
Vertices arrive one at a time; must color immediately.
Quality bounds are weaker than offline.
In compilers: variables that are simultaneously live are adjacent in the interference graph. Color = register.
If χ ≤ number of registers, all variables fit.
If not: spill some to memory.
This is one of the original motivations for graph coloring research.
Tasks that conflict (need same resource at same time) are adjacent. Color = time slot.
Course timetabling: courses with shared students conflict. Exam scheduling: same logic.
Cell towers that interfere are adjacent. Color = frequency.
Reduces interference.
A Sudoku puzzle is graph coloring with 9 colors on a specific 81-vertex graph.
Original motivation. Adjacent regions get different colors.
Four colors suffice for any planar map.
For real-world coloring:
Backtracking finds optimum.
DSATUR + local search.
Greedy + local search.
Some graph classes have polynomial algorithms:
Bounds on χ(G):
χ(G) ≥ ω(G). The largest clique requires that many colors.
For perfect graphs, equality. In general, can be much higher.
A relaxation. χ_f ≤ χ.
Counts the number of proper k-colorings.
For connected G that is not complete or odd cycle: χ(G) ≤ Δ(G) (max degree).
For graph with degree sequence d₁ ≥ d₂ ≥ ... ≥ d_n: greedy uses at most max_i min(d_i + 1, i) colors.
Real-world graphs often have structure that helps:
The hard cases are dense, irregular, adversarial graphs.
For large graphs, χ(G) is usually impossible to find exactly.
Greedy fails on adversarial inputs. DSATUR usually robust.
If your problem has structure (interval graph, bipartite), use specialized algorithms.
Simple greedy often suffices. Get baseline before complex methods.
Each color class is an independent set. Coloring = partition into independent sets.
Coloring complement = clique cover.
Related but different. Both NP-hard.
For most applications, NetworkX greedy + local search suffices.
Understanding graph coloring teaches:
The applications (register allocation, scheduling) are practical and important.