A school has to set the dates of its written exams. Two exams cannot be on the same day if at least one student is enrolled in both. What is the minimum number of days needed? Whoever runs a radio network must assign frequencies to transmitters so that two neighbouring transmitters do not interfere. A compiler must decide which variables to place in the same processor registers.
Three problems far apart from each other, with a single structure: graph colouring.
The problem
We build a graph whose vertices are the objects to place (exams, transmitters, variables) and whose edges connect pairs in conflict. A colouring assigns each vertex a colour so that two adjacent vertices have different colours. The colours represent resources: days, frequencies, registers.
The minimum sufficient number of colours is called the chromatic number, written χ(G). Minimising colours means minimising resources.
Some well-known cases:
- a graph with no edges has χ = 1;
- a bipartite graph with at least one edge has χ = 2, and this is easy to check with a breadth-first search;
- a cycle with an odd number of vertices needs 3 colours;
- a complete graph with n vertices, where everything conflicts with everything, needs n colours.
Why it is hard
Deciding whether a graph can be coloured with 3 colours is an NP-complete problem: no algorithm is known that solves it in polynomial time in the general case. For graphs of a few dozen vertices a well-pruned exhaustive search works; for hundreds or thousands of vertices, as in real timetables, heuristics are used that give good colourings without a guarantee of optimality.
A useful lower bound: if the graph contains a clique of k vertices, all in conflict with one another, at least k colours are needed. If a heuristic finds a colouring with the same number of colours as the largest clique found, you know for certain that the optimum has been reached.
The greedy algorithm
The simplest method: take the vertices in some order and give each one the lowest colour not used by its already coloured neighbours.
def greedy_coloring(adj, order):
color = {}
for v in order:
used = {color[u] for u in adj[v] if u in color}
c = 0
while c in used:
c += 1
color[v] = c
return color
It guarantees at most Δ + 1 colours, where Δ is the maximum degree of the graph. The result, however, depends heavily on the order. There are bipartite graphs, colourable with 2 colours, for which an unlucky order leads greedy to use as many colours as there are vertices on one side.
Two orders that work better than a random one:
- decreasing degree (Welsh-Powell): first the vertices with the most conflicts, which are the hardest to place;
- degeneracy order: repeatedly remove the vertex of minimum degree and colour in reverse order; this guarantees at most d + 1 colours, where d is the degeneracy, often much smaller than Δ.
DSatur
The DSatur heuristic (degree of saturation) dynamically chooses the next vertex to colour: the one with the largest number of different colours already present among its neighbours. On ties, the one with more uncoloured neighbours. The idea is to deal first with the most constrained vertices, before they run out of options.
On many practical graphs DSatur gives clearly better results than plain greedy, at a still modest cost. On bipartite graphs it always finds a 2-colouring.
Example: an exam timetable
| Exam | Conflicts with |
|---|---|
| Calculus | Physics, Chemistry, Computing |
| Physics | Calculus, Chemistry |
| Chemistry | Calculus, Physics, Biology |
| Computing | Calculus |
| Biology | Chemistry |
Calculus, Physics and Chemistry form a three-vertex clique: at least 3 days are needed. DSatur colours Calculus (day 1), then Chemistry (day 2), then Physics (day 3), then Biology (day 1, no conflict with Calculus) and Computing (day 2). Three days are enough, and the clique proves you cannot do better.
Applications beyond timetables
- Register allocation: the compiler builds an interference graph between variables that are live at the same moment; with k registers available it looks for a k-colouring and, if it cannot find one, moves some variables to memory.
- Frequencies: neighbouring transmitters get different channels; in practice, Wi-Fi networks in a building are planned exactly this way, with the few non-overlapping channels as colours.
- Maps: colouring the regions of a map so that neighbouring regions have different colours. For planar maps the four colour theorem guarantees that four always suffice.
- Sudoku: each cell is a vertex, connected to the cells in the same row, column and box; solving it means completing a 9-colouring starting from the given partial one.
Variants that matter in reality
Real timetables are rarely a pure colouring. There are rooms with limited capacity, teachers unavailable on certain days, preferences for spreading out exams from the same course. Usually you start from a good colouring and improve it with local search or metaheuristics, treating hard constraints as mandatory and soft ones as penalties to minimise.
In short
- Colouring assigns resources to conflicting objects: days, frequencies, registers.
- Finding the chromatic number is hard in general, but cliques give lower bounds.
- Greedy is simple and fast; its result depends strongly on the vertex order.
- DSatur colours the most constrained vertices first and often gives better results.
- In real timetables, colouring is the starting point, refined with constraints and penalties.
