Helpful context:

In 1852, Francis Guthrie tried to color a map of England’s counties so that no two adjacent counties shared the same color. He noticed four colors always seemed to be enough - no matter how complicated the map, he couldn’t find a counterexample requiring five. He asked his brother, who asked his professor, who asked nobody else for 124 years. When the answer finally came, it required a computer to check 1,834 cases. It was the first major theorem in mathematics proved with computer assistance, and it remains controversial in some circles today.

That’s graph coloring: a question simple enough to pose on a napkin, hard enough to hold off professional mathematicians for over a century, and practically important enough to show up in compilers, scheduling algorithms, and Sudoku solvers.

The Setup

Assign a color to each vertex of a graph so that no two adjacent vertices share the same color. The chromatic number $\chi(G)$ is the minimum number of colors needed.

Some basic observations before any algorithms:

  • A complete graph $K_n$ requires $n$ colors - every pair of vertices is adjacent.
  • A triangle-free graph can still have arbitrarily large chromatic number (the Mycielski construction builds such graphs).
  • $\chi(G) \geq \omega(G)$ where $\omega(G)$ is the size of the largest clique - a $k$-clique forces $k$ distinct colors. But the gap between the clique number and chromatic number can be as large as you want.

2-Coloring: The Easy Case

A graph is 2-colorable if and only if it is bipartite - contains no odd-length cycle.

The algorithm is BFS or DFS: color the source vertex with color 1, then alternate colors as you explore. If you ever try to assign a vertex two different colors, you’ve found an odd cycle. Otherwise, you have a valid 2-coloring.

This runs in $O(V + E)$ time and $O(V)$ space. It’s optimal - you have to look at every edge. 2-colorability is one of the simplest graph problems imaginable.

3-Coloring: The Hard Case

Deciding whether $\chi(G) \leq 3$ is NP-complete. The jump from 2 to 3 is a computational phase transition.

The NP-hardness proof is one of the most elegant reductions in complexity theory. We reduce from 3-SAT.

Given a 3-CNF formula with variables $x_1, \ldots, x_n$, build a graph as follows.

Variable gadgets. Add a global “palette” vertex $p$. For each variable $x_i$, add two vertices $v_i^T$ (true) and $v_i^F$ (false). Connect:

  • $v_i^T$ to $v_i^F$ (they must get different colors)
  • $v_i^T$ to $p$ and $v_i^F$ to $p$ (neither gets the palette color)

With three colors playing the roles of TRUE, FALSE, and BASE: the palette vertex gets BASE; each literal vertex gets TRUE or FALSE. Setting $x_i = $ true means $v_i^T$ gets TRUE color and $v_i^F$ gets FALSE color.

Clause gadgets. For each clause $(\ell_1 \vee \ell_2 \vee \ell_3)$, add a small OR-gadget - five extra vertices and seven edges - that is properly 3-colorable if and only if at least one of $\ell_1, \ell_2, \ell_3$ gets the TRUE color.

The result: the graph $G_\varphi$ is 3-colorable if and only if $\varphi$ is satisfiable. The reduction runs in polynomial time.

This also shows 4-COL, 5-COL, and $k$-COL for any $k \geq 3$ are NP-complete - take a 3-coloring instance and add a $(k-3)$-clique connected to all existing vertices.

Greedy Coloring

The simplest algorithm: fix an ordering of the vertices, process them one by one, assign each vertex the smallest color not used by any already-colored neighbor.

Theorem. Greedy uses at most $\Delta + 1$ colors, where $\Delta$ is the maximum degree.

The proof is one line: when we color vertex $v$, it has at most $\Delta$ already-colored neighbors, so at most $\Delta$ colors are forbidden, and color $\Delta + 1$ is always available.

This bound is achievable - a star graph has $\Delta = n-1$ and clearly needs only 2 colors, but a bad ordering gives $n$ colors. The bound is tight in the worst case, not a guarantee of optimality.

Better orderings. The degeneracy $d(G)$ of a graph is the smallest $k$ such that every subgraph has a vertex of degree $\leq k$. Process vertices in degeneracy order (repeatedly peel off minimum-degree vertices, process in reverse order) and greedy uses at most $d(G) + 1$ colors. For planar graphs, $d \leq 5$, giving a 6-coloring greedily. For forests, $d \leq 1$, giving a 2-coloring.

Brooks' Theorem

Greedy gives $\Delta + 1$ colors. Can we do better in general?

Theorem (Brooks, 1941). Every connected graph that is neither a complete graph nor an odd cycle satisfies $\chi(G) \leq \Delta(G)$.

The exceptions are tight: $K_n$ requires $n = \Delta + 1$ colors, and odd cycles require 3 colors with $\Delta = 2$. For everything else, $\Delta$ colors suffice.

The proof idea: if the graph isn’t regular, a careful BFS ordering from a non-maximum-degree vertex gives a greedy $\Delta$-coloring directly. If the graph is regular, you find two non-adjacent neighbors of the root vertex, use them as the starting anchor, and construct an ordering where greedy never needs the $(\Delta+1)$-th color.

Brooks' theorem gives an efficient $\Delta$-coloring algorithm for all non-exceptional graphs.

The Four Color Theorem

Every planar graph is 4-colorable.

Guthrie’s observation from 1852 was finally proved in 1976 by Kenneth Appel and Wolfgang Haken - with a computer. The proof reduced the problem to checking whether any of 1,834 specific graph configurations could appear as a “bad” subgraph. No human checked all 1,834 cases; a computer did.

The proof structure uses two ideas:

  • Unavoidability: every planar graph must contain at least one configuration from a specific finite list.
  • Reducibility: each configuration on the list, if it appeared in a minimal counterexample to 4-colorability, would lead to a contradiction - a smaller non-4-colorable planar graph.

If every configuration is reducible and the list is unavoidable, there are no counterexamples, and the theorem holds.

Discomfort check. The four color theorem proof checked thousands of cases by computer. Is that a real proof?

This was genuinely controversial in 1976. Some mathematicians argued that a proof no human can read isn’t really a proof - it’s an empirical observation verified by a machine that might have bugs. Today the consensus has shifted: yes, it’s a valid proof. The case analysis was verified by multiple independent implementations. A simpler computer-assisted proof by Robertson, Sanders, Seymour, and Thomas in 1997 reduced the cases to about 600. The mathematical content is real; the computer is just doing case analysis that would take a human several lifetimes.

The Five Color Theorem has an elegant human-readable proof using Euler’s formula and Kempe chains, and is worth knowing even though we now have the stronger result.

The Chromatic Polynomial

For a graph $G$, the chromatic polynomial $P_G(k)$ counts the number of proper $k$-colorings of $G$. It is literally a polynomial in $k$.

For a path on $n$ vertices: $P_G(k) = k(k-1)^{n-1}$. The first vertex has $k$ choices; each subsequent vertex has $k-1$ choices (avoid the previous one).

For a cycle $C_n$: $P_G(k) = (k-1)^n + (-1)^n (k-1)$.

The chromatic number $\chi(G)$ is the smallest positive integer $k$ for which $P_G(k) > 0$. Computing the chromatic polynomial is $#P$-hard - harder than just deciding $\chi(G)$.

Applications

Register allocation in compilers. When a compiler assigns variables to CPU registers, it needs to ensure two variables whose values are both needed at the same moment get different registers. Build the interference graph: one vertex per variable, one edge between two variables whose live ranges overlap. Register allocation is exactly graph coloring with $k$ = number of registers. NP-completeness means optimal allocation is hard in general; real compilers use greedy heuristics with “spilling” (storing overflow variables in memory).

Exam scheduling. Each exam is a vertex; two exams conflict if the same student is enrolled in both. Color vertices with time slots. Minimizing the number of time slots = minimizing the chromatic number. Greedy approaches work well in practice; exact solvers handle small instances.

Frequency assignment in wireless networks. Radio transmitters that are geographically close enough to interfere must be assigned different frequencies. This is graph coloring with transmitters as vertices and interference as edges. Minimizing the spectrum required = minimizing the chromatic number.

Sudoku. A Sudoku puzzle is a precolored $9 \times 9$ grid where each cell gets one of 9 digits, subject to row, column, and box constraints. The constraint structure is equivalent to graph coloring: the “graph” has 81 vertices (cells), edges between cells that share a row, column, or box, and chromatic number exactly 9. Solving Sudoku = finding a valid 9-coloring of this specific graph consistent with the given constraints.

Summary

Problem Complexity Best known algorithm
2-coloring (bipartiteness) $P$ BFS/DFS, $O(V+E)$
3-coloring NP-complete Exponential exact; best approx uses $\tilde{O}(n^{0.2})$ colors
$k$-coloring, $k \geq 3$ NP-complete Same hardness as 3-coloring
Greedy with $\Delta+1$ colors $P$ $O(V+E)$
$\Delta$-coloring (Brooks) $P$ $O(V+E)$ (non-exceptional graphs)
4-coloring planar graphs $P$ $O(V)$ (follows from four color theorem)
Chromatic polynomial $#P$-hard Exponential exact

The story of graph coloring compresses the arc of theoretical computer science into a single problem: a simple question, an easy special case, a hard general case, an NP-completeness proof through reduction, a celebrated theorem requiring computer assistance, and a landscape of approximation results where even a small increase in the required number of colors creates a phase transition in difficulty.

Read next: