The Intrinsic Complexity of Graph Colouring in Structured Graphs — Epoche C2
What the maximum degree does and does not determine The chromatic number $\chi(G)$ of a graph — the fewest colours that can be put on its vertices so that no edge joins two of the same colour — is bounded above by the maximum degree $\Delta(G)$ whenever $G$ is connected and is neither a complete graph nor an odd cycle. That is Brooks' theorem of 1941, and it is the source of a working assumption that runs through the practical literature: that the densest local neighbourhood in a graph is a reasonable proxy for how hard the graph is to colour. This essay is about how far that proxy can be from the truth, in which direction it fails, and what the actual determinant of $\chi$ turns out to be in the graph classes where the question has been settled. Start with what is easy and true. Colour the vertices greedily in any fixed order, giving each vertex the least-indexed colour not already used on its earlier neighbours. A vertex has at most $\Delta$ neighbours altogether, so at most $\Delta$ colours can be blocked and the $(\Delta+1)$-th is always free. Hence $$\chi(G) \le \Delta(G) + 1$$ for every graph, with no hypotheses at all. Brooks' theorem says that the $+1$ can be dropped except in two families, and its proof is a refinement of exactly this argument, which is worth setting out because it shows what the exceptions are for. Suppose first that $G$ is connected and not regular, so some vertex $v$ has $\deg(v) \le \Delta - 1$. Order the vertices by non-increasing distance from $v$, with $v$ last. Every vertex $u \ne v$ has a neighbour strictly nearer to $v$, and that neighbour therefore comes later in the order, so at most $\deg(u) - 1 \le \Delta - 1$ of $u$'s neighbours precede it and a colour from a palette of $\Delta$ remains free. The vertex $v$ comes last but has at most $\Delta - 1$ neighbours in total. So $\Delta$ colours suffice. The regular case is the hard one, and it is where the exceptions live. If $G$ is $\Delta$-regular, connected, not complete and not an odd cycle, with $\Delta \ge 3$, one can find a vertex $v$ with two non-adjacent neighbours $a$ and $b$ such that removing $a$ and $b$ leaves the graph connected. Colour $a$ and $b$ first, with the same colour — legitimate, since they are not adjacent — and then order the remaining vertices by non-increasing distance from $v$ within $G - a - b$, with $v$ last. The earlier argument applies unchanged to every vertex except $v$, and $v$ itself is saved by the trick: it has $\Delta$ neighbours, but two of them share a colour, so at most $\Delta - 1$ colours are blocked. The remaining case $\Delta \le 2$ is a path or a cycle, and an even cycle or path needs two colours. The two exceptions are thus not accidents of the statement: complete graphs and odd cycles are precisely the connected graphs in which no such pair $a$, $b$ can be found. How far $\Delta$ can be from $\chi$, and in which direction Brooks' theorem is an upper bound, and the question of whether $\Delta$ is a good proxy is the question of how loose that bound can be. Here the earlier version of this essay went wrong in a way worth correcting explicitly, because the error is a natural one and it inverts the whole picture. It claimed that one can build a graph — a long path with a large clique attached — whose maximum degree is small while its clique number $\omega(G)$, the number of vertices in its largest complete subgraph, is large, and that in such a graph $\omega$ rather than $\Delta$ governs the colouring. No such graph exists. If $G$ contains a clique on $k$ vertices, each of those $k$ vertices has at least $k-1$ neighbours inside the clique alone, so $\Delta(G) \ge \omega(G) - 1$. Combined with the trivial lower bound $\omega \le \chi$ — a clique needs a distinct colour per vertex — and the greedy bound, every graph satisfies $$\omega(G) \;\le\; \chi(G) \;\le\; \Delta(G) + 1 .$$ The clique number can never outrun the maximum degree; it is pinned beneath it. And in the specific construction offered, a path attached to $K_r$ at one clique vertex, that vertex has degree $(r-1) + 1 = r$, so $\Delta = r$ while $\chi = \omega = r$: Brooks' bound is exactly tight there, not loose. The example proved the opposite of what it was asked to prove. The bound is loose in the other direction, and unboundedly so. Take the complete bipartite graph $K_{n,n}$: every vertex has degree $n$, so $\Delta = n$, while two colours suffice, so $\chi = 2$. The gap $\Delta - \chi = n - 2$ grows without limit. The same happens for the star $K_{1,n}$, and for trees generally. This is the correct form of the complaint against $\Delta$: it is a valid ceiling that can sit arbitrarily far above the floor. Nor is the difficulty repaired by a more refined degree parameter. The natural refinement is the degeneracy $d(G)$, the largest minimum degree over all subgraphs of $G$; a $d$-degenerate graph can be coloured with $d+1$ colours by repeatedly stripping a vertex of degree at most $d$ and colouring in reverse. But $K_{n,n}$ has minimum degree $n$, so its degeneracy is also $n$, and the refinement gains nothing. The point generalises: any parameter computed from degrees alone must give the same value on $K_{n,n}$ as on any other $n$-regular graph, and $n$-regular graphs include both bipartite graphs with $\chi = 2$ and graphs with $\chi$ as large as $n+1$. Degree information simply does not determine $\chi$. One further claim in the earlier text needs withdrawing rather than repairing. It suggested that a graph with low maximum degree containing a large independent set illustrates the inadequacy of $\Delta$. It does not, and the inequality runs the wrong way: since a proper colouring partitions the $n$ vertices into $\chi$ independent sets, each of size at most the independence number $\alpha(G)$, we have $n \le \chi\alpha$, that is $\chi \ge n/\alpha$. A large independent set weakens this lower bound; it is a small $\alpha$ that forces many colours. On $C_5$, the five-cycle, $n = 5$ and $\alpha = 2$