xix. Graph Coloring

Vertex colouring is easy for $k=2$ (bipartite) and NP-complete for $k=3$, even on planar graphs. Exact chromatic number for $n\le 23$ is $O(2^{n}n)$ by inclusion–exclusion; the chromatic polynomial for $n\le 18$ is $O(2^n{n}^3)$; structured classes (chordal, interval, perfect) are polynomial (Special Graphs). Edge colouring needs $\Delta$ colours on bipartite graphs (König, constructive) and $\Delta$ or $\Delta +1$ on simple graphs (Vizing, constructive $\Delta +1$).

Bounds

Bound	Statement
clique	$\chi \ge \omega$
independence	$\chi \ge n/\alpha$
greedy	$\chi \le \Delta +1$ in any order
degeneracy	$\chi \le d+1$, $d$ = max over subgraphs of the min degree (colour in reverse smallest-last order)
Brooks	$\chi \le \Delta$ unless $G$ is a complete graph or an odd cycle
planar	$\chi \le 4$ (5 constructively in linear time)
perfect graphs	$\chi =\omega$

Proof: greedy and degeneracy bounds

Greedy gives each vertex the smallest colour not used by its already-coloured neighbours; it has at most $\mathrm{deg}v\le \Delta$ of them, so some colour in $\{0..\Delta \}$ is free. For degeneracy, repeatedly remove a minimum-degree vertex (degree $\le d$ in the remaining graph) and colour in reverse removal order: when a vertex is coloured, its coloured neighbours are those removed after it, at most $d$ of them. $\chi \ge n/\alpha$ because each colour class is an independent set of size $\le \alpha$.

Heuristics: Welsh–Powell (sort vertices by degree descending once, then greedy-colour in that fixed order) is the simplest named heuristic and already realises the degeneracy-style bound in practice on many graphs, though it can be beaten by adversarial orderings since the order is static. DSATUR (colour next the vertex with the most distinct colours among its neighbours, ties by degree) re-picks the order dynamically as colours are assigned, is exact on bipartite graphs, and is strictly stronger in practice; combined with a clique lower bound and backtracking it solves $n\approx 100$ sparse instances.

Complexity by class: deciding $\chi \le 2$ is $O(V+E)$ (BFS bipartiteness check); deciding $\chi \le 3$ is NP-complete even restricted to planar graphs — the same 2-vs-3 cliff as 2-SAT vs 3-SAT; computing $\chi$ exactly is NP-hard and inapproximable within $n^{1-\epsilon }$ for any $\epsilon >0$ unless P = NP; $\chi (\text{tree})=2$ (or 1 if edgeless); $\chi =\omega$ exactly on interval and chordal graphs (greedy by left endpoint / perfect elimination order respectively).

Interval graphs are the class that appears most in contests, almost always disguised as “minimum number of rooms/machines/platforms” rather than named as colouring — recognise it and the problem collapses to maximum simultaneous overlap, swept in $O(n\log n)$ (Interval Problems).

Exact chromatic number in $O(2^{n}n)$

$G$ is $k$-colourable iff the number of ordered $k$-tuples of independent sets covering $V$ is nonzero, and by inclusion–exclusion that number is ${\sum }_{S\subseteq V}(-1{)}^{n-|S|}I(S{)}^k$, where $I(S)$ = number of independent subsets of $S$ (including $\varnothing$).

int chromaticNumber(const vector<int>& adj) {               // adj[v] = neighbour bitmask, n <= ~23
    int n = sz(adj), N = 1 << n; if (!n) return 0;
    const ull P = (1ULL << 61) - 1;                            // exact count mod a large prime; false "0" is negligible
    auto mulmod = [&](ull a, ull b) { __uint128_t c = (__uint128_t)a * b; ull r = (ull)(c & P) + (ull)(c >> 61); return r >= P ? r - P : r; };
    vector<ull> I(N), pw(N, 1); I[0] = 1;
    for (int S = 1; S < N; S++) { int v = __builtin_ctz(S); I[S] = I[S ^ 1 << v] + I[(S ^ 1 << v) & ~adj[v]]; }
    for (int k = 1; k <= n; k++) {
        ull tot = 0;
        for (int S = 0; S < N; S++) {
            pw[S] = mulmod(pw[S], I[S] % P);
            tot = ((n - __builtin_popcount(S)) & 1) ? (tot + P - pw[S]) % P : (tot + pw[S]) % P;
        }
        if (tot) return k;
    }
    return n;
}

Proof: the inclusion–exclusion count and the recurrence for $I$

$I(S{)}^k$ counts $k$-tuples of independent sets all contained in $S$. A tuple whose union is exactly $U$ is counted for every $S\supseteq U$ with total sign ${\sum }_{S\supseteq U}(-1{)}^{n-|S|}=[U=V]$. So the alternating sum counts tuples covering $V$; such a tuple exists iff $V$ splits into $k$ independent sets (take differences of the sets). $I(S)=I(S\setminus v)+I(S\setminus N[v])$: independent subsets of $S$ either avoid $v$ or contain $v$ and none of its neighbours.

Method	Time	Practical $n$
inclusion–exclusion above	$O(2^{n}n)$	20–25, the best known exact asymptotic
bitmask DP: dp[mask] = min colours to cover mask, transitioning over maximal independent submasks	$O(3^n)$, or $O(2^{n}n)$ with [[06-bit-manipulation/03-submasks-and-sos-dp	SOS]] preprocessing of which subsets are independent
try $k=1,2,3,\dots$ with DSATUR + clique lower bound + backtracking	exponential, no clean bound	100+ on sparse instances

Chromatic polynomial

$P(x)$ = number of proper colourings with at most $x$ colours. Deletion–contraction: $P(G)=P(G-e)-P(G/e)$. Closed forms: trees $x(x-1{)}^{n-1}$, cycles $(x-1{)}^n+(-1{)}^n(x-1)$, $K_n$: $x^{\underline{n}}$, chordal graphs $\prod (x-d_i)$. $|P(-1)|$ counts acyclic orientations (Stanley). For general graphs with $n\le 18$: $P(x)={\sum }_j{e}_j\left(\genfrac{}{}{0ex}{}{x}{j}\right)$ where $e_j$ = number of ordered partitions of $V$ into $j$ nonempty independent sets, computed by a ranked (subset-convolution style) inclusion–exclusion in $O(2^n{n}^3)$.

struct ChromaticPolynomial {                                 // mint = modular integer type
    int n; vector<mint> E;                                   // E[j]: ordered covers by j disjoint nonempty independent sets
    ChromaticPolynomial(const vector<int>& g) : n(sz(g)), E(n + 1) {
        int full = 1 << n; vector<char> indep(full, 1);
        for (int s = 1; s < full; s++) { int v = __builtin_ctz(s), r = s & (s - 1); indep[s] = indep[r] && !(g[v] & r); }
        vector<vector<mint>> f(n + 1, vector<mint>(full));    // f[r][T] = # independent r-subsets of T
        for (int s = 0; s < full; s++) if (indep[s]) f[__builtin_popcount(s)][s] = 1;
        for (int r = 0; r <= n; r++) for (int i = 0; i < n; i++) for (int s = 0; s < full; s++) if (s >> i & 1) f[r][s] += f[r][s ^ 1 << i];
        vector<vector<mint>> q(n + 1);
        for (int s = 0; s < full; s++) {                      // [y^j] q_n = [z^n] (sum_{r>=1} f[r][s] z^r)^j
            int t = __builtin_popcount(s); q[0] = {mint(1)};
            for (int m = 1; m <= n; m++) {
                q[m].assign(m + 1, mint(0));
                for (int r = 1; r <= min(m, t); r++) { mint a = f[r][s]; if (a == mint(0)) continue; for (int j = 0; j < sz(q[m - r]); j++) q[m][j + 1] += a * q[m - r][j]; }
            }
            for (int j = 0; j <= n; j++) { mint e = j < sz(q[n]) ? q[n][j] : mint(0); if ((n - t) & 1) E[j] -= e; else E[j] += e; }
        }
    }
    mint operator()(ll x) const { mint res = 0, b = 1; for (int j = 0; j <= n; j++) { res += E[j] * b; b = b * (mint(x) - mint(j)) / mint(j + 1); } return res; }
};

Proof sketch: the ranked inclusion–exclusion

A proper colouring with at most $x$ colours is an assignment of the vertex set to an ordered sequence of $j$ nonempty colour classes chosen from $x$ colours: $P(x)={\sum }_j{e}_j\left(\genfrac{}{}{0ex}{}{x}{j}\right)$. $e_j$ counts ordered $j$-tuples of disjoint nonempty independent sets with union $V$; disjointness plus covering $V$ is equivalent to “sizes sum to $n$ and the union is $V$”. Inclusion–exclusion over the allowed ground set $T$ removes the union condition, and tracking total size by the variable $z$ enforces disjointness (size sum $n$ with union inside $T$ and union $=V$ forces a partition). For fixed $T$, $\sum$ over tuples of $z^{\text{total size}}=({\sum }_{r\ge 1}{f}_r(T)z^r{)}^j$, and the DP $q$ extracts $[z^n]$ of all powers at once.

Edge colouring

Bipartite (König): exactly $\Delta$ colours. Simple constructive method in $O(nm)$: for each edge $(u,v)$ take a colour $a$ free at $u$ and $b$ free at $v$; if $a\ne b$, flip the $a/b$ alternating path starting at $v$ (it cannot reach $u$ in a bipartite graph), then colour $(u,v)$ with $a$.

vector<int> bipartiteEdgeColoring(int L, int R, const vector<pair<int, int>>& E) {   // multigraph; colours in [0, Δ)
    int n = L + R, D = 0; vector<int> deg(n);
    for (auto [a, b] : E) D = max({D, ++deg[a], ++deg[L + b]});
    vector<vector<int>> at(n, vector<int>(D, -1));           // at[v][c] = edge id with colour c at v
    vector<int> col(sz(E), -1);
    auto other = [&](int e, int v) { return v == E[e].first ? L + E[e].second : E[e].first; };
    for (int e = 0; e < sz(E); e++) {
        int u = E[e].first, v = L + E[e].second, a = 0, b = 0;
        while (at[u][a] >= 0) a++;
        while (at[v][b] >= 0) b++;
        if (a != b) {                                         // flip the a/b path starting at v
            vector<int> path; int x = v, c = a;
            while (at[x][c] >= 0) { int f = at[x][c]; path.push_back(f); x = other(f, x); c ^= a ^ b; }
            for (int f : path) { int p = E[f].first, q = L + E[f].second; at[p][col[f]] = at[q][col[f]] = -1; }
            for (int f : path) { col[f] ^= a ^ b; int p = E[f].first, q = L + E[f].second; at[p][col[f]] = at[q][col[f]] = f; }
        }
        col[e] = a; at[u][a] = at[v][a] = e;
    }
    return col;
}

For $m$ up to $10^5$–$10^6$ (Library Checker “Bipartite Edge Coloring”), make the graph $\Delta$-regular by merging low-degree vertices and adding dummy edges, then recursively split: an even-degree regular bipartite graph splits into two halves by alternating colours along Euler circuits (Euler Tours); an odd degree peels off one perfect matching (Hopcroft–Karp) first: about $O(m\log m)$ in practice.

Simple graphs (Vizing): $\Delta +1$ colours suffice, found in $O(nm)$ by fan rotations and alternating-path flips; deciding whether $\Delta$ suffices is NP-hard.

vector<int> vizing(int n, const vector<pair<int, int>>& E) {   // simple graph; colours in [0, Δ]
    vector<int> cc(n + 1), res(sz(E)), fan(n), freeC(n), loc;
    for (auto [u, v] : E) cc[u]++, cc[v]++;
    int K = *max_element(all(cc)) + 1;
    vector<vector<int>> adj(n, vector<int>(K, -1));           // adj[u][c] = neighbour joined by colour c
    for (auto [u, v0] : E) {
        int v = v0, at = u, end = u, d, c = freeC[u], ind = 0, i = 0;
        fan[0] = v; loc.assign(K, 0);
        while (d = freeC[v], !loc[d] && (v = adj[u][d]) != -1) loc[d] = ++ind, cc[ind] = d, fan[ind] = v;
        cc[loc[d]] = c;
        for (int cd = d; at != -1; cd ^= c ^ d, at = adj[at][cd]) swap(adj[at][cd], adj[at][cd ^ c ^ d]), end = at;
        while (adj[fan[i]][d] != -1) { int l = fan[i], r = fan[++i], e = cc[i]; adj[u][e] = l; adj[l][e] = u; adj[r][e] = -1; freeC[r] = e; }
        adj[u][d] = fan[i]; adj[fan[i]][d] = u;
        for (int y : {fan[0], u, end}) { int& z = freeC[y] = 0; while (adj[y][z] != -1) z++; }
    }
    for (int i = 0; i < sz(E); i++) { auto [u, v] = E[i]; while (adj[u][res[i]] != v) res[i]++; }
    return res;
}

Proof: König's edge colouring theorem (the flip never hits $u$)

Colour $a$ is free at $u$, $b$ is free at $v$, $a\ne b$, and $a$ is used at $v$. The maximal path starting at $v$ with colours $a,b,a,\dots$ is unique (each vertex has at most one edge of each colour). Since $u$ and $v$ are on opposite sides, along this path the edges coloured $a$ always go from $v$‘s side to $u$‘s side and the edges coloured $b$ go back; so the path can only enter $u$‘s side by an $a$-edge, and it can’t enter $u$ because $a$ is free at $u$. Swapping $a$ and $b$ on the path keeps the colouring proper (at the far end of the path the swapped-in colour was free, by maximality) and makes $a$ free at $v$, so $(u,v)$ gets colour $a$. With $\Delta$ colours each endpoint always has a free colour before its edge is coloured, so $\Delta$ colours suffice.
Vizing ($\Delta +1$): the fan argument — rotate the fan of neighbours of $u$ whose edges can shift colours, and if stuck, flip a $c/d$ alternating path from $u$; a counting argument with $\Delta +1$ colours ensures one of these succeeds. The code implements this standard proof.

Variants worth naming

Variant	Note
List colouring	each vertex has its own allowed colour set — strictly harder than ordinary colouring
Equitable colouring	colour classes must be nearly equal in size
Fractional chromatic number	the LP relaxation of colouring; polynomial for perfect graphs
Total colouring	colour vertices and edges together, no shared colour between adjacent/incident elements

Where this shows up beyond contests: register allocation in compilers (the classic application), scheduling under pairwise conflicts (exams, meetings, frequency assignment), map colouring (planar, hence $\le 4$), and Sudoku (a colouring of a specific 81-vertex graph with 9 colours).