The order decides the colours

Every earlier argument here about colouring maps has been about what is possible: that four colours always suffice on a map in the plane, that five can be proved by a short chain argument, that the number of colourings is a polynomial. None of them says how a person with a map and a box of crayons should actually go about it.

The method everyone uses without thinking is greedy. Take the regions — or, in the language of graphs, the vertices — in some order. Give each the lowest-numbered colour that none of its already-coloured neighbours has. Never go back.

Greedy colouring is fast, obviously correct, and never produces a clash. It is also the clearest example there is of an algorithm whose output depends entirely on something that looks like an irrelevant detail: the order in which it is handed the vertices. On one graph it can use two colours or four, on another three or five, and the difference is nothing but the sequence.

Two colours, or four, from the same graph #

The crown graph is two-coloured by eye: every edge runs between the top row and the bottom row, so the top row can all be one colour and the bottom row another. Greedy colouring finds that if it is handed the top row first. The first vertex gets colour 1; the next three top vertices have no coloured neighbours and also get colour 1; then every bottom vertex is joined to some top vertex and gets colour 2. Two colours, which is optimal.

Now hand it the vertices alternately — top 1, bottom 1, top 2, bottom 2 and so on, pairing each top vertex with the bottom vertex not joined to it. Top 1 gets colour 1. Bottom 1 is not joined to top 1, so it also gets colour 1. Top 2 is joined to bottom 1, which has colour 1, so it gets colour 2; bottom 2 is joined to top 1 but not top 2, so it too gets colour 2. Each new pair is joined to every earlier pair and gets a fresh colour. Four pairs, four colours.

The same trap scales. On the crown graph with $n$ vertices on each side, the alternating order forces $n$ colours on a graph that needs two. A greedy colouring can be arbitrarily worse than the best one, not by a constant factor but by any factor at all, and the graph gives no warning: every vertex looks like every other, and the order that ruins everything is just a way of reading the picture.

The bound it can never break #

For all its sensitivity, greedy colouring cannot do arbitrarily badly in one respect. When a vertex’s turn comes, the colours it must avoid are the colours on its neighbours, and a vertex with $d$ neighbours can see at most $d$ colours. So colour $d + 1$ is always available. If the largest degree in the graph is $\Delta$, greedy colouring never uses more than $\Delta + 1$ colours, in any order.

That is a genuine theorem with a two-line proof, and it is the first thing anyone learns about colouring graphs. In the crown graph it is not much use: every vertex has degree three, so the bound is four, which the bad order reaches exactly. The bound is also the ancestor of a much older argument. Seven regions on a doughnut needed an upper bound on the colours any map on a torus requires, and the route there is the same idea applied to a whole surface at once: Euler’s formula caps the average degree, so some vertex always has few neighbours, and greedy colouring with that vertex last never runs short. Heawood’s bound for every surface is this counting, pushed as far as it will go. What changes from surface to surface is only how large the guaranteed small degree is.

It is the other end of the range that is harder to pin down. How often does greedy colouring find the true answer, and how far is the typical order from the best one?

On the Petersen graph the answer is reassuring: most orders find the best colouring and the rest are one colour off. There is not much room to fail, since the chromatic number is three and the bound is four.

An order that always works exists #

There is always some order in which greedy colouring finds the true answer. Take a best colouring, list all the vertices of colour 1 first, then all of colour 2, and so on. When greedy reaches a colour-1 vertex, none of its neighbours has been coloured yet — they are all in later classes, since a colour class has no internal edges — so it gets colour 1. A colour-2 vertex has neighbours of colour 1 at most among the earlier ones, so it gets colour 1 or 2. Inductively, greedy never uses a colour beyond the one the best colouring assigned.

The argument is short enough to check on the crown graph itself. Its best colouring has two classes, the top row and the bottom row; listing one class and then the other is precisely the order that produced two colours in the opening figure. The alternating order is what happens when the classes are interleaved.

So the search for a best colouring is a search for a good order, and there are $n!$ orders. That reformulation explains why the problem is hard rather than solving it — deciding whether a graph can be three-coloured is one of the standard NP-complete problems, and nothing known does fundamentally better in the worst case than searching — but it shows that greedy colouring’s failure is always a failure of the order, never of the rule.

On the icosahedron the typical order does worse. The bound $\Delta + 1$ is six and the truth is four, and a random order most often lands in between. A small fraction of orders use all six colours, which is the bound reached on a graph that needs only four. The gap between a random greedy colouring and the best one grows with the gap between $\Delta + 1$ and the chromatic number, and on large sparse graphs that gap can be large.

Choosing the order well: smallest last #

There is a simple rule for choosing an order that does much better than chance on many graphs, and it turns the $\Delta + 1$ bound into something sharper.

Remove a vertex of smallest degree from the graph. Then remove a vertex of smallest degree from what is left, and so on until nothing remains. Now colour greedily in the reverse of that removal order — the last vertex removed first.

The point is what each vertex sees when its turn comes. The neighbours already coloured are exactly the neighbours that were still present when it was removed, and it was removed at a moment when it had the fewest neighbours of anything left. So if at every stage of the removal some vertex has at most $k$ neighbours remaining, greedy in reverse uses at most $k + 1$ colours. The smallest such $k$ is the graph’s degeneracy, and it can be far below the largest degree: a star with a thousand leaves has largest degree a thousand and degeneracy one, and smallest-last colours it with two.

For planar graphs this gives six colours at once, since Euler’s formula guarantees a vertex of degree at most five in every planar graph and in every piece of one. That argument is the first half of the five-colour proof, and the chain argument there is exactly what it takes to shave the sixth colour off. The figure shows the order doing better than its guarantee: every vertex of the icosahedron has degree five, so the bound is six, and this particular smallest-last order found four.

When Δ colours are enough, and the two exceptions #

The bound $\Delta + 1$ is reached by greedy colouring in the worst order, but is it ever the true chromatic number? It is for two kinds of graph, and for no others.

An odd cycle has every vertex of degree two, and going round it with two colours alternating fails on return, because the length is odd: it needs three. A complete graph on $n$ vertices has every vertex of degree $n - 1$ and needs all $n$ colours, since every pair is joined. Both need $\Delta + 1$.

Brooks’s theorem, proved by Leonard Brooks in 1941, says these are the only connected graphs that do. Every other connected graph can be coloured with $\Delta$ colours. The proof is itself a careful choice of greedy order: find two non-adjacent neighbours $u$ and $w$ of some vertex $v$ such that removing $u$ and $w$ leaves the graph connected, colour $u$ and $w$ first with the same colour, then colour the rest in an order that ends at $v$ and in which every other vertex has a later neighbour. Every vertex but $v$ then meets at most $\Delta - 1$ coloured neighbours, and $v$ meets $\Delta$ neighbours using at most $\Delta - 1$ colours between them, since two of them share one. The exceptions are exactly the graphs where no such $u$ and $w$ can be found.

Brooks was one of the four Cambridge undergraduates who, a year earlier, had turned squared rectangles into electrical circuits. Both results came out of the same small group, working on puzzles.

Colouring as the vertices arrive #

There are settings in which the order is not chosen at all, because the vertices arrive one at a time and each must be coloured on arrival — a new exam added to a timetable, a new frequency request, a new job needing a machine. This is online colouring, and it is greedy colouring with the order chosen by an adversary.

The crown graph shows how bad that can be, but the online version is worse than any single bad order suggests, because the adversary can adapt to the colours already chosen. Even on forests — graphs with no cycles at all, which two colours always suffice for — an adversary presenting the vertices one at a time can force any online method to use a number of colours that grows like the logarithm of the number of vertices, by building trees whose roots have been given every colour seen so far and then joining them. It is the same phenomenon as matching as the vertices arrive: the online method pays for its ignorance of the future, and the price can be measured exactly.

There are families where greedy colouring in a natural order is perfect. For interval graphs — each vertex a time interval, joined when two intervals overlap, which is how lectures compete for rooms — colouring greedily in order of starting time uses exactly as many colours as the largest number of intervals overlapping at one moment, and no colouring can use fewer. It is why a room timetable can be built by a clerk working through the day in order, and it is the rare case where the obvious order is also the best one.

Why anyone colours graphs greedily #

The reason greedy colouring matters is that it is what people and programs actually do, in settings where the colours are resources and a clash is a collision.

A school timetabling its exams has a graph whose vertices are exams, joined when some student sits both; a colour is a time slot, and a proper colouring is a timetable in which nobody is expected in two rooms at once. A compiler deciding which values to keep in a processor’s few registers has a graph whose vertices are values, joined when two are needed at the same moment; a colour is a register. A radio regulator has transmitters joined when they are close enough to interfere, and colours are frequencies. In every case the number of colours is a cost — slots, registers, spectrum — and in every case the graph is far too large to search.

So the questions this essay asks of small graphs are the questions those settings live with. How much does the order matter? A great deal: the crown graph is a caricature, but graphs with the same trap inside them occur in practice, and a timetable built in a careless order can use many more slots than it needs. Is there a good order to use? Smallest-last is one of several heuristics that do well; largest-first, colouring the most constrained vertices while there is still room, is another. Can a fast method guarantee near-optimal results? No, as the last section explains — which is why these heuristics are judged by how they perform on the graphs that occur rather than by any worst-case promise.

Register allocation adds a twist that the pictures here do not show. When a program needs more values at once than there are registers, the graph needs more colours than are available, and some values must be moved out to memory — “spilled” — at a cost. The greedy order then decides not just how many colours are used but which values get spilled, and good compilers choose the order with that in mind.

What the orders cannot show #

The random-order charts sample orders; they do not list them. The Petersen graph has $10! = 3{,}628{,}800$ orders and the icosahedron $12!$, about 479 million, and the percentages are estimates from five thousand of each — accurate to about a percentage point, and silent about orders too rare to be sampled. The chromatic numbers beside them are not estimates: they were found by trying every colouring with fewer colours and failing. That distinction matters for reading the charts. A bar at three colours on the Petersen graph means that at least one order was seen reaching three; the claim that three is the fewest possible is a separate fact, established by a search that tried to two-colour the graph and could not — a search that would have succeeded, and been reported, had the graph been bipartite.

The figures also cannot show the thing that makes colouring hard in general. On these small graphs a good order is easy to find by trying a few; on large graphs the orders number in the astronomical and the good ones can be exponentially rare. That no efficient method is known to find them — or to decide whether a graph can be three-coloured at all — is a statement about all graphs at once, and no picture of a small graph illustrates it.

Still open: how well any fast method can do #

Greedy colouring, in any order a fast rule can choose, can be far from optimal, and the question is whether any fast method can do much better. The answer, as far as anyone can prove, is no. Unless P = NP, no efficient algorithm can colour every graph within a factor of $n^{1-\varepsilon}$ of the chromatic number, for any fixed $\varepsilon > 0$ — so on large graphs, efficient colouring can be almost as far from optimal as greedy in its worst order.

The sharpest open cases are small. Given a graph known to be three-colourable, how few colours can an efficient algorithm guarantee? The best methods known use a number of colours that grows like a small power of the number of vertices — about $n^{0.2}$ — while the best impossibility results rule out only a constant, five. Between a constant and a power of $n$ there is a gap nobody has closed, for the simplest non-trivial case of the simplest colouring problem. And the practical methods used on real timetables and real compilers are, underneath, greedy colourings in cleverly chosen orders — smallest-last, largest-first, or orders that pick next the vertex whose neighbours already use the most distinct colours — refined by local search. They work well on the graphs that occur, and nothing explains precisely why those graphs are easy.