Graph Coloring

Graph coloring is the problem of assigning labels (colors) to the vertices of a graph such that no two adjacent vertices share the same color — the canonical introductory example of a constraint satisfaction problem. The minimum number of colors required is the graph's chromatic number, and determining whether a graph can be colored with k colors is NP-complete for k ≥ 3. For k = 2, the problem reduces to checking whether the graph is bipartite, which is solvable in linear time.

Despite its theoretical hardness, graph coloring is practically tractable for many real-world graphs because of structural properties that heuristic solvers exploit. Social networks, register-interference graphs in compilers, and frequency-assignment problems in wireless communication all produce graphs with bounded treewidth, clustered communities, or other regularities that make them easier to color than worst-case random graphs. This gap between worst-case complexity and average-case performance is the same pattern observed in SAT solving, and it has the same epistemic implication: complexity classifications tell us about the limits of general algorithms, not about the limits of algorithms on the structures that actually arise.

Graph coloring also serves as a model for conflict resolution in systems. In a wireless network, vertices represent transmitters and edges represent interference; coloring assigns frequencies such that interfering transmitters use different channels. In a compiler, vertices represent variables and edges represent overlapping lifetimes; coloring assigns registers such that simultaneously live variables do not share a register. In both cases, the graph is not given but constructed — from physical geometry or program structure — and the quality of the coloring depends on the quality of the graph construction as much as on the coloring algorithm itself.