Graph Colouring

Assign colours to vertices so that adjacent vertices differ. The chromatic number $\chi (G)$ is the minimum number of colours.

The complexity

Question	Complexity
Is $\chi \le 2$? (bipartiteness)	$O(V+E)$ — BFS 2-colouring
Is $\chi \le 3$?	NP-complete, even for planar graphs
Compute $\chi$	NP-hard
Approximate $\chi$	inapproximable within $n^{1-\epsilon }$
$\chi$ of a tree	2 (or 1 if edgeless)
$\chi$ of a planar graph	$\le 4$ (Four Colour Theorem); deciding $\le 3$ is NP-complete
$\chi$ of an interval graph	= max clique; greedy by left endpoint
$\chi$ of a chordal graph	= max clique; perfect elimination ordering
Edge colouring	${\chi }^{\prime }\in \{\Delta ,\Delta +1\}$ (Vizing); deciding which is NP-complete
Edge colouring, bipartite	${\chi }^{\prime }=\Delta$ (König); constructible in polynomial time

The 2-vs-3 cliff mirrors 2-SAT vs 3-SAT — checking bipartiteness is trivial, one colour more is NP-complete.

Bounds

Bound	Statement
$\chi \ge \omega$	at least the max clique size
$\chi \le \Delta +1$	greedy, any order
Brooks	$\chi \le \Delta$ unless $G$ is complete or an odd cycle
$\chi \le 1+{\max }_{\text{ordering}}\min (\mathrm{deg})$	degeneracy + 1
$\chi \ge n/\alpha$	$\alpha$ = independence number
Planar	$\chi \le 4$
Perfect graphs	$\chi =\omega$

Degeneracy is the useful practical bound: order the vertices by repeatedly removing a minimum-degree vertex, then colour greedily in reverse. Uses at most $d+1$ colours where $d$ is the degeneracy — often far below $\Delta +1$.

Greedy colouring

vector<int> greedyColour(int n, vector<vector<int>>& adj, vector<int>& order) {
    vector<int> colour(n, -1);
    for (int u : order) {
        vector<bool> used(n + 1, false);
        for (int v : adj[u]) if (colour[v] >= 0) used[colour[v]] = true;
        int c = 0;
        while (used[c]) c++;
        colour[u] = c;
    }
    return colour;
}

The ordering determines the quality. Useful orderings:

Ordering	Guarantee
Arbitrary	$\Delta +1$
Largest degree first	often good in practice
Degeneracy (smallest-last)	$d+1$ colours
DSATUR (most saturated first)	optimal for bipartite and several other classes
Perfect elimination (chordal graphs)	optimal

DSATUR — always colour the vertex with the most distinctly-coloured neighbours — is the best simple heuristic and is often optimal on structured graphs.

Exact chromatic number

Method	Time	$n$
Try $k=1,2,3,\dots$ with backtracking + DSATUR	exponential	50-100
Bitmask DP over independent sets	$O(3^n)$ or $O(2^{n}n)$	20
Inclusion-exclusion (Björklund-Husfeldt)	$O(2^{n}n)$	20-25
Branch and bound + clique lower bound	exponential	100+ (sparse)

The $O(2^{n}n)$ inclusion-exclusion

$G$ is $k$-colourable iff the number of ways to cover $V$ with $k$ (possibly overlapping) independent sets is non-zero:

${\sum }_{S\subseteq V}(-1{)}^{|V\setminus S|}i(S{)}^k>0,$

where $i(S)$ is the number of independent subsets of $S$ — computable for all $S$ by a $O(2^n)$ DP. Elegant, and the best known exact algorithm.

Bitmask DP over independent sets

dp[mask] = minimum colours to cover mask; transition over maximal independent submasks. $O(3^n)$, or $O(2^{n}n)$ with SOS preprocessing of which subsets are independent.

Variants

Variant	Note
Edge colouring	colour the line graph; ${\chi }^{\prime }\le \Delta +1$ (Vizing)
List colouring	each vertex has its own allowed set; harder than ordinary colouring
Equitable colouring	colour classes of nearly equal size
Fractional chromatic number	LP relaxation; polynomial for perfect graphs
Total colouring	vertices and edges together
Colouring with $\le k$ colours, $k$ fixed	still NP-complete for $k\ge 3$
Interval graph colouring	= maximum overlap — see Interval Partitioning

Interval graphs are the case that appears most in contests, usually disguised as “minimum number of rooms/machines/platforms”. There, $\chi =\omega$ = maximum simultaneous overlap, and a sweep solves it in $O(n\log n)$.

Where colouring appears

• Register allocation in compilers — the classic application.
• Scheduling with conflicts — exams, meetings, frequencies.
• Map colouring — planar, hence $\le 4$.
• Sudoku — a colouring of a specific 81-vertex graph with 9 colours.
• Timetabling, frequency assignment, partitioning into independent sets.

The practical checklist

1. Is it bipartite? → 2 colours, $O(V+E)$.
2. Is it a tree or forest? → 2 colours.
3. Is it an interval graph? → $\chi =\omega$, sweep.
4. Is it planar? → $\le 4$ colours; 5-colouring is constructible in linear time.
5. Is $n\le 20$? → bitmask DP.
6. Otherwise → DSATUR + branch and bound, or accept a heuristic.

See also: Bipartite Graphs · Maximum Clique · Interval Partitioning