Chapter 14 · Special Topics
Graph Colouring
Greedy bounds, Brooks' and Reed's theorems, chromatic number versus clique number, and the three colouring problems that are actually solvable.
#Four parameters, one paragraph
A proper k-colouring assigns colours to vertices so that adjacent vertices differ. χ(G) = the minimum k; ω(G) = clique number; Δ(G) = maximum degree; g(G) = girth.
Four inequalities, all proved by one paragraph
- χ(G) ≥ ω(G) (a clique needs all-different colours),
- χ(G) ≤ Δ + 1 (greedy: when you colour a vertex, at most Δ colours are forbidden),
- χ(G) ≤ ⌊ 1/2 + √(2m + 1/4) ⌋ (greedy in degeneracy order: χ ≤ degeneracy + 1 ≤ √(2m) + 1),
- χ(G) ≤ degeneracy(G) + 1, where degeneracy = maxH ⊆ G δ(H) is found by repeatedly deleting a minimum-degree vertex. Since the degeneracy is at most ⌊ √(2m) ⌋, this subsumes the previous bound on sparse graphs — and it is the only one of the four that is useful in code.
#Brooks’ theorem
If G is connected with maximum degree Δ, then χ(G) ≤ Δ unless G is a complete graph or (for Δ = 3) an odd cycle.
Both exceptions need Δ + 1: KΔ+1 has Δ+1 mutually adjacent vertices, and C2k+1 needs 3 colours with Δ = 2. Otherwise take a vertex v with two non-adjacent neighbours x,y (exists because G is not a clique; for Δ=2 the path/cycle case is immediate). Order the vertices so that x, y come last and every other vertex has a later neighbour — a reverse BFS/leaf-elimination order works. Colour greedily in the reverse of that order. Every vertex other than v has a later neighbour, so when it is coloured at most Δ - 1 colours are forbidden — one of Δ remains. The clean finish: give x and y the same colour first (they are non-adjacent), then colour the remaining vertices in reverse BFS order rooted at {x,y}, with v last. Every vertex coloured before v has a neighbour coloured earlier, so at most Δ - 1 colours are forbidden at its turn; and when v is coloured, its Δ neighbours use at most Δ - 1 colours because x and y share one. So Δ colours suffice. ∎
#What a solver actually does
- 2-colouring = bipartiteness, O(n+m) by BFS (Bipartite Graphs and 2-Colouring). Exact and the only case that is polynomial for general graphs,
- 3-colouring is NP-complete even for max-degree-4 graphs, but polynomial for: bipartite (trivial), interval and chordal graphs (perfect: χ = ω, greedy on a perfect elimination order — Independent Sets, Cliques, and Treewidth), planar with girth ≥ 5 (Grötzsch: 3-colourable), and fixed graphs (4 colours suffice for every planar graph, Planarity and Euler's Formula, but finding a 4-colouring is O(n2) with the deep algorithm; the elementary route is 5-colouring by the min-degree-≤-5 argument),
- list colouring / DP colouring for bounded treewidth, and edge colouring by Vizing (χ' ≤ Δ + 1; bipartite edge colouring = Δ exactly — König's line-colouring theorem, which is matching again, Bipartite Matching (Kuhn's Algorithm)).
#Greedy colouring in degeneracy order
// degeneracy ordering + greedy: always optimal on chordal/interval, within 1 of Brooks elsewhere
vector<int> order, col(n, -1);
{
vector<int> deg(n); for (int v = 0; v < n; v++) deg[v] = g[v].size();
vector<vector<int>> buckets(max_deg + 1);
for (int v = 0; v < n; v++) buckets[deg[v]].push_back(v);
vector<char> removed(n);
for (int b = 0; b <= max_deg; b++)
while (buckets[b].size()) {
int v = buckets[b].back(); buckets[b].pop_back();
if (removed[v]) continue;
removed[v] = 1; order.push_back(v);
for (int to : g[v]) if (!removed[to] && deg[to] > b) { deg[to]--; buckets[deg[to]].push_back(to); }
}
}
for (int i = n - 1; i >= 0; i--) { // reverse order = colour the "hard" ones first
vector<char> used(k + 1);
for (int to : g[order[i]]) if (col[to] != -1) used[col[to]] = 1;
for (int c = 0; c <= k; c++) if (!used[c]) { col[order[i]] = c; break; }
}#Where colouring statements bite
- "Colour the graph with the fewest colours" on an interval graph is the same as "maximum overlap" — greedy on endpoints, not a colouring algorithm; recognising that your object is an interval graph is the whole problem,
- Edge colouring is not vertex colouring of the line graph in complexity terms (χ' ≤ Δ+1 vs Vizing's Class 1/2 distinction), and for bipartite graphs χ' = Δ — the "schedule exams in the fewest slots with k exams per room" family is exactly this,
- the probabilistic method bounds (χ ≥ (n)/(2tlog n) from independence numbers, Ramsey Theory on Graphs's counting twin) are how you prove "there is a graph with ω = 2 and χ arbitrarily large" (the Mycielski construction is the explicit version — triangle graphs with high χ, worth knowing as the counterexample to "χ is bounded by ω and n"),
- if a problem gives a game (two players colour alternately, "can First force a proper colouring with k colours?") that is the game chromatic number — no theorem helps; small k is decided by a strategy-stealing/pairing argument.
#Exercises
- Prove χ(G) ≤ Δ2/2 + Δ + 1 for triangle-free G using a greedy + Rödl trick (or count: each colour class has size ≥ n/(Δ+1)...).
- Mycielski: from G build G' by adding a vertex zu for each u adjacent to all neighbours of u, plus one universal vertex. Show χ(G') = χ(G) + 1 and ω(G') = ω(G) + 1 — the operation that turns "no triangle, χ = 3" into anything.
- Show that a graph with degeneracy d has a greedy colouring in d+1 colours in which each colour class has size ≥ (n)/(d+1), and deduce α(G) ≥ (n)/(d+1) (Caro–Wei is the sharper ∑v (1)/(deg(v)+1)).