---
title: "Graph Colouring"
summary: Greedy bounds, Brooks' and Reed's theorems, chromatic number versus clique number, and the three colouring problems that are actually solvable.
difficulty: core
tags: [coloring, greedy, np-complete]
prereq: [foundations/bipartite, trees/dfs]
see: [complexity/npc-graphs, special/ramsey]
---

## Four parameters, one paragraph

:::definition label="Terms"
A **proper $k$-colouring** assigns colours to vertices so that adjacent vertices differ. $\chi(G)$ = the minimum $k$; $\omega(G)$ = clique number; $\Delta(G)$ = maximum degree; $g(G)$ = girth.
:::

:::props title="Four inequalities, all proved by one paragraph"
- $\chi(G) \ge \omega(G)$ (a clique needs all-different colours),
- $\chi(G) \le \Delta + 1$ (greedy: when you colour a vertex, at most $\Delta$ colours are forbidden),
- $\chi(G) \le \lfloor 1/2 + \sqrt{2m + 1/4} \rfloor$ (greedy in **degeneracy** order: $\chi \le \mathrm{degeneracy} + 1 \le \sqrt{2m} + 1$),
- $\chi(G) \le \mathrm{degeneracy}(G) + 1$, where degeneracy $= \max_{H \subseteq G} \delta(H)$ is found by repeatedly deleting a minimum-degree vertex. Since the degeneracy is at most $\lfloor \sqrt{2m} \rfloor$, this subsumes the previous bound on sparse graphs — and it is the only one of the four that is *useful in code*.
:::

## Brooks’ theorem

:::theorem title="Brooks (1941)"
If $G$ is connected with maximum degree $\Delta$, then $\chi(G) \le \Delta$ unless $G$ is a complete graph or (for $\Delta = 3$) an odd cycle.
:::

:::proof
Both exceptions need $\Delta + 1$: $K_{\Delta+1}$ has $\Delta+1$ mutually adjacent vertices, and $C_{2k+1}$ needs 3 colours with $\Delta = 2$. Otherwise take a vertex $v$ with two non-adjacent neighbours $x,y$ (exists because $G$ is not a clique; for $\Delta=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 $\Delta - 1$ colours are forbidden — one of $\Delta$ 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 $\Delta - 1$ colours are forbidden at its turn; and when $v$ is coloured, its $\Delta$ neighbours use at most $\Delta - 1$ colours because $x$ and $y$ share one. So $\Delta$ colours suffice. ∎
:::

## What a solver actually does

:::note title="What a solver actually does"
- **2-colouring** = bipartiteness, $O(n+m)$ by BFS (@foundations/bipartite). 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: $\chi = \omega$, greedy on a perfect elimination order — @special/independent), **planar** with girth ≥ 5 (Grötzsch: 3-colourable), and fixed graphs (4 colours suffice for every planar graph, @special/planar, but *finding* a 4-colouring is $O(n^2)$ 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 ($\chi' \le \Delta + 1$; bipartite edge colouring $= \Delta$ exactly — König's line-colouring theorem, which is matching again, @matching/bipartite).
:::

## Greedy colouring in degeneracy order

```cpp greedy-colour.cpp
// 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

:::warning title="Where colouring statements bite"
1. "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,
2. **Edge** colouring is not vertex colouring of the line graph in complexity terms ($\chi' \le \Delta+1$ vs Vizing's Class 1/2 distinction), and for bipartite graphs $\chi' = \Delta$ — the "schedule exams in the fewest slots with $k$ exams per room" family is exactly this,
3. the **probabilistic method** bounds ($\chi \ge \frac{n}{2t\log n}$ from independence numbers, @special/ramsey's counting twin) are how you prove "there is a graph with $\omega = 2$ and $\chi$ arbitrarily large" (the Mycielski construction is the explicit version — triangle graphs with high $\chi$, worth knowing as the counterexample to "$\chi$ is bounded by $\omega$ and $n$"),
4. 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

:::exercise title="Three exercises, all one paragraph"
1. Prove $\chi(G) \le \Delta^2/2 + \Delta + 1$ for triangle-free $G$ using a greedy + Rödl trick (or count: each colour class has size $\ge n/(\Delta+1)$...).
2. Mycielski: from $G$ build $G'$ by adding a vertex $z_u$ for each $u$ adjacent to all neighbours of $u$, plus one universal vertex. Show $\chi(G') = \chi(G) + 1$ and $\omega(G') = \omega(G) + 1$ — the operation that turns "no triangle, $\chi = 3$" into anything.
3. Show that a graph with degeneracy $d$ has a greedy colouring in $d+1$ colours in which each colour class has size $\ge \frac{n}{d+1}$, and deduce $\alpha(G) \ge \frac{n}{d+1}$ (Caro–Wei is the sharper $\sum_v \frac{1}{\deg(v)+1}$).
:::

:::problems
- [[CSES 1668]] Building Teams | https://cses.fi/problemset/task/1668 | easy | the 2-colouring case, in public
- [[CSES 1684]] Giant Pizza | https://cses.fi/problemset/task/1684 | core | 2-SAT, i.e. "2-colouring with clauses" — see @special/twosat
:::