How Few Colours Do You Need? A Puzzle That Runs Timetables

Take a collection of points with lines joining some pairs, which is what mathematicians call a graph, and assign a colour to each point so that no two points joined by a line share a colour. The question is how few colours suffice, and that minimum is a property of the graph called its chromatic number. The formulation is abstract deliberately, because an enormous range of practical problems reduce to it once the right thing is taken as a point and the right relationship as a line. Anything where items must be separated because they conflict, and where the conflicts are known, becomes this problem, and the minimum number of colours becomes the minimum number of slots, channels or resources required.

The applications are numerous and the translation in each case is direct:

• •Exam timetabling, where examinations are points and a shared student is a conflict
• •Radio frequency assignment, where transmitters that would interfere must differ
• •Register allocation in compilers, where variables live simultaneously and cannot share storage
• •Scheduling meetings where people cannot be in two at once
• •Sudoku, which is exactly a colouring problem on a specific graph
• •Map colouring, where regions sharing a border must differ

The most famous instance concerns maps drawn on a flat surface, where the question is whether four colours always suffice so that regions sharing a border differ. The conjecture was raised in 1852, resisted proof for over a century, and was settled in 1976 by Appel and Haken with a proof that reduced the problem to checking a large but finite number of configurations and then checked them by computer. That method provoked a genuine philosophical argument, since no human could verify the case analysis directly, and the question of whether a proof nobody can read is a proof was debated seriously. Independent verifications have since been produced, including one checked by a formal proof assistant in 2005, which addresses the objection about human verification by shifting it to trust in the verifying software.

The simplest practical approach is worth describing because it shows where the difficulty hides. Take the points in some order and give each the lowest-numbered colour not already used by any of its neighbours, which is fast and always produces a valid colouring. The number of colours it uses depends entirely on the order chosen, and there always exists an order for which it produces the true minimum, which sounds encouraging and is useless because finding that order is as hard as the original problem. Heuristics choose orders that tend to work well, including taking the most connected points first, and they do reasonably in practice. The gap between a method that always works and one that always works well is the whole subject, and it recurs across combinatorial optimisation.

Determining the minimum number of colours for an arbitrary graph is computationally hard in a precise technical sense, meaning no method is known that solves it efficiently for all inputs and finding one would resolve a central open problem. Even deciding whether three colours suffice is hard, while deciding whether two suffice is easy, which is a sharp and characteristic boundary. Practical work therefore uses methods that find good rather than optimal colourings, including greedy approaches that colour points one at a time in a chosen order, which are fast and whose quality depends heavily on that order. For structured problems arising in practice, specialised methods exploit the structure and do far better than the general difficulty suggests, which is why exam timetables get produced despite the underlying problem being intractable.

Colouring points so that joined points differ is the same problem as scheduling anything where conflicts are known, with the minimum number of colours giving the minimum number of slots. Four colours suffice for any flat map, proved in 1976 by computer case analysis that provoked an argument about what a proof is. The general problem is computationally hard, and practical methods settle for good rather than optimal.