Graph colouring
Also known as: Graph coloring · graph colouring · vertex colouring · chromatic number · greedy colouring · DSatur · Welsh–Powell algorithm · smallest last · degeneracy · four colour theorem
Colour the blocks of Almaty so that neighbours differ in colour, or cast the roles of War and Peace so that no actor has to meet their own other character in one chapter. Greedy colouring is simple, but its number of colours depends on the order; the right order gives a provable bound, and the exact answer is a hard problem, yet solvable on real maps and timetables.
Below are 2681 blocks of central Almaty, the pieces of the city between streets. Let us colour the map so that blocks sharing a street get different colours. This is graph colouring: blocks are vertices, a shared street is an edge. The simplest way is to take the blocks one at a time and give each the first colour its already coloured neighbours do not have. Going west to east it uses six colours. Switch methods: the order of the walk changes the number of colours, and exact search finds four.
Four is also the lower bound: turn on “Four neighbours pairwise” and the scene circles the places where four blocks are each neighbours of each. There are 159 such places, and three colours cannot fit there. Four colours always suffice for maps, which is a famous theorem, but it was proved with a computer, and the algorithm that follows from the proof is far from simple. There are, however, simple ways to colour with five and six, with a proof of why they work.
The idea
Graph colouring is assigning colours to vertices so that the ends of every edge differ. The smallest number of colours with which this can be done is the chromatic number χ. The greedy way goes over the vertices in some order and gives each the smallest colour free of its already coloured neighbours. It is never wrong about correctness, since neighbours always differ, but its number of colours depends on the order, sometimes heavily. The whole trick is in the order.
Colouring is a common language for problems of the “neighbours must differ” kind. Exams with shared students go on different days. Variables alive at the same time go into different processor registers. Neighbouring towers get different frequencies. Characters who meet in one chapter go to different actors. A colour is a day, a register, a frequency, an actor, and the chromatic number is how many of them are needed at least.
Greedy colouring and the order
Greedy colouring in any order uses at most Δ + 1 colours, where Δ is the largest number of neighbours of a vertex.
When the turn comes to vertex v, at most deg(v) ≤ Δ of its neighbours are coloured, and they take up at most Δ colours. Among Δ + 1 colours at least one is free, and the greedy way will take a colour no greater than Δ + 1.
For the map of Almaty this is a weak bound: one block has 38 neighbours, a huge block surrounded by small ones, and the bound promises 39 colours. The greedy way uses six or seven depending on the order. A hundred random orders from the listing give 6 colours 62 times and 7 colours 38 times. But a good order always exists.
For any graph there is an order of the vertices in which greedy colouring uses exactly χ colours.
Take some colouring in χ colours and list the vertices like this: first all the vertices of colour 1, then all of colour 2, and so on. We prove that the greedy way gives each vertex a colour no greater than it had in the original colouring. Suppose this holds for all vertices before v, and v had colour c. Its already coloured neighbours come earlier in the order, so their original colours are less than c: v has no neighbours of its own colour. By the assumption their greedy colours are also less than c. So among the colours 1, …, c at least colour c is free, and v gets a colour no greater than c. In all there will be at most χ colours, and fewer is impossible.
True, writing out such an order needs an optimal colouring, which is what we are looking for. So in practice orders that are easy to compute are used. The oldest is vertices with the most neighbours first: the hard vertices get a colour while the choice is still wide. This was proposed in 1967 by Dominic Welsh and Martin Powell, and on the blocks of Almaty it gives five colours instead of six.
Smallest last
The order can also be chosen from the other end. Find the vertex with the fewest neighbours and put it at the very end: when its turn comes it has few neighbours, and a free colour will be found. Remove it from the graph and repeat: in the remaining graph again find the vertex with the fewest remaining neighbours and put it before the previous one. Colour in the reverse order of removal. This is the smallest-last order.
Let d be the largest of the numbers “how many neighbours a vertex still had when it was removed”. It is called the degeneracy of the graph.
Greedy colouring in the smallest-last order uses at most d + 1 colours.
When vertex v is coloured, exactly those of its neighbours are coloured that were removed after it: the colouring order is the reverse of the removal order. These neighbours were still in the graph when v was removed, so there are no more of them than v had remaining neighbours at that moment, and that number is at most d. So at most d colours are taken, and among d + 1 there is a free one.
For the blocks of Almaty d = 4: on removal a block never had more than four neighbours left, and the order guarantees five colours, which is exactly how many it uses. The reason for such low degeneracy is that the map is flat.
A planar graph has degeneracy at most 5, so smallest last colours any map with at most six colours.
A simple planar graph with V ≥ 3 vertices has at most 3V − 6 edges: this is a consequence of Euler’s formula, proved in “Mathematics, the Queen of the Sciences” in the chapter on graphs. The sum of the vertex degrees is twice the number of edges, that is, at most 6V − 12 < 6V. So the average degree is less than six, and there is a vertex of degree at most 5. With two vertices or fewer this is obvious. Any subgraph of a planar graph is also planar, so it too has such a vertex. Hence on removal each vertex has at most five neighbours left, d ≤ 5, and there are at most six colours.
DSatur: the most constrained next
The order does not have to be fixed in advance. In 1979 Daniel Brélaz proposed choosing the next vertex on the fly: the one whose neighbours already have the most different colours. This is the most constrained vertex: if it is put off, it will only have fewer free colours. Ties go to the vertex with more neighbours. The method was named DSatur, from “degree of saturation”.
On the blocks of Almaty DSatur uses five colours, like smallest last. For bipartite graphs it always finds a two-colouring, and in general it is often the best of the simple methods. But it has no provable bound like that of the smallest-last order: the first problem of the article has a graph of ten vertices with degeneracy 2 on which DSatur uses four colours, although smallest last manages with three.
The exact answer
Finding the chromatic number is a hard problem: in 1972 Richard Karp put it on the list of 21 NP-complete problems, and nobody knows a fast algorithm for all graphs. But hard in the worst case does not mean hopeless in practice. Two bounds narrow the search from both sides. From below, a clique: if q vertices are pairwise joined, they need q colours. From above, any colouring found by the greedy way.
The rest is done by backtracking: vertices in DSatur order, each tries the allowed colours, and at a dead end we go back and change the colour of the previous one. Two kinds of pruning make it fast. Colours beyond k are not taken when checking whether k are enough. And of the colours not yet used, only one is tried: they are all alike, and colourings that differ only in their names are the same colouring. On the blocks of Almaty the search proves that four colours are enough after examining 2721 positions.
A clique does not always give the answer. Five vertices in a cycle contain no triangle, yet they need three colours. There are triangle-free graphs that need any number of colours: in 1955 Jan Mycielski showed how to build them, and the smallest such graph with chromatic number 4, the Grötzsch graph of eleven vertices, is among the tests of the second problem. For small graphs there is also an exact method without search: the inclusion–exclusion formula counts in how many ways the vertices are covered by k independent sets, in 2V steps for each k. The second problem is about it.
Code
The map of blocks: neighbours are blocks that go round the same stretch of street. Greedy colouring in three orders and in a hundred random ones, smallest last, DSatur and exact search for four colours, which is the same DSatur going back at dead ends. Fours of pairwise neighbouring blocks are counted straight from the neighbour lists.
blocks: 2681, neighbour pairs: 6292, most neighbours: 38 greedy, west to east 6 colours greedy, 100 random orders 6 colours 62 times, 7 colours 38 times greedy, most neighbours first 5 colours smallest last 5 colours (at most 4 neighbours coloured before a block) DSatur 5 colours four blocks touch pairwise in 159 places, so 3 colours are not enough exact search, 4 colours: possible (2721 positions)
The second graph comes from the novel. Imagine a staging of War and Peace in which an actor can play several roles if those characters never meet in one chapter. The 46 most prominent characters, two roles clash if the characters are ever in the same chapter: this is a colouring where a colour is an actor. The model is crude: a character “is in a chapter” if they are named there at least twice, and being named in a conversation does not mean appearing on stage. But the graph comes out dense and honestly hard.
Twelve roles meet pairwise, Prince Andrei, Pierre, Natasha, Nikolai Rostov, Kutuzov, Napoleon and the other main figures, so fewer than twelve actors is impossible. The greedy methods take 13–14 actors. The search proves that twelve are not enough after examining 365 positions, and finds a casting for thirteen in 47. The chromatic number here is one more than the clique.
roles: 46, clashing pairs: 419, most rivals: 40 (Prince Andrei) greedy, by first appearance 14 actors greedy, by mentions 14 actors greedy, by rivals (Welsh-Powell) 13 actors DSatur 13 actors 12 roles clash pairwise, so fewer than 12 actors is impossible exact search, 12 actors: impossible (365 positions) exact search, 13 actors: possible (47 positions)
What it costs
| Method | Time | Guarantee |
|---|---|---|
| greedy in a given order | O(V + E) | at most Δ + 1 |
| most neighbours first (Welsh–Powell) | O(V log V + E) | at most maxi min(di + 1, i) over the vertices in this order |
| smallest last | O(V + E) with buckets | at most d + 1; 6 on flat maps |
| DSatur | O((V + E) log V) with a heap | optimal on bipartite graphs; not in general |
| backtracking | exponential in the worst case | the exact answer |
| inclusion–exclusion | O(2V·V) | the exact answer, V up to 20–25 |
The bound for the Welsh–Powell order is proved like the first claim: the i-th vertex has at most i − 1 coloured neighbours and at most di, its degree. In practice all the simple methods run in fractions of a second on graphs with millions of vertices, and the time goes on the exact answer. Approximating the chromatic number with a guarantee is not possible either: it is known that even an answer correct up to a factor of V1−ε is as hard to find as the exact one.
Where it works
- Compilers. Variables needed at the same time cannot live in one register. The “alive at the same time” graph is coloured with as many colours as the processor has registers; if that is not enough, some variable goes to memory. Gregory Chaitin proposed doing it this way in 1981, and register allocators in many compilers are built on it. More in the basic course chapter on the compiler.
- Timetables. Exams with shared students, lectures by one teacher, matches of one team: vertices joined by a conflict, and a colour is a day or a slot. Welsh and Powell wrote their paper precisely about timetables.
- Frequencies and channels. Neighbouring transmitters, Wi-Fi access points, base stations go on different frequencies, or they interfere. This is the first problem of the article.
- Parallel computing. If vertices of one colour are not neighbours, they can be updated at the same time: nobody reads what a neighbour writes. This is how iterative methods on grids are parallelised, with the red-black colouring of a chessboard’s cells.
- Puzzles. Sudoku is a colouring of a graph of 81 cells in nine colours, where some colours are already given, and the neighbours are the cells of one row, column or box.
History
In 1852 Francis Guthrie, colouring a map, noticed that four colours were enough, and asked whether this is always so. In 1879 Alfred Kempe published a proof, and for eleven years it was thought correct, until Percy Heawood found a mistake in it. From Kempe’s ideas Heawood extracted a proof for five colours. Four colours were proved only in 1976 by Kenneth Appel and Wolfgang Haken: a computer checked almost two thousand configurations, and this was the first major proof that a person could not check by hand. In 1997 Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas simplified it, and in 2005 Georges Gonthier checked the whole proof in the Coq proof assistant. This story is told in more detail in “Mathematics, the Queen of the Sciences”, in the chapter on graphs.
The algorithmic side began later. In 1967 Welsh and Powell proposed the order “most neighbours first” for timetables, in 1979 Brélaz DSatur, and in 1983 David Matula and Leland Beck described the smallest-last order and how to find it in linear time. In 1972 Karp proved that the chromatic number is NP-hard, and since then colouring has been one of the main proving grounds for heuristics and exact search.
Problems
In the first problem frequencies have to be given to towers with the guarantee “at most d + 1”, and no greedy order except smallest last gives it. In the second, the exact number of days for an exam session of twenty exams: the clique and DSatur go wrong, and the inclusion–exclusion formula does not.
Frequencies for the towers Exam daysData: Almaty roads © OpenStreetMap contributors, ODbL War and Peace by Leo Tolstoy, public domain