FOUR COLOURS FOR ANY MAP, FOUND IN LINEAR TIME

Any map drawn on a flat sheet can be coloured with four colours so that neighbouring countries never share one. Francis Guthrie conjectured it in 1852; Appel and Haken proved it in 1976. But the theorem only says that four colours exist. How do you find them for a given map? “There is no easy answer,” write Yuta Inoue, of the University of Tokyo, and five colleagues from Japan, Canada, Slovenia and Denmark. It has been so tangled that it led to many proposed counterexamples: maps for which nobody could find four colours.

Dots, lines and triangles

Each country becomes a dot, or vertex, and each shared border a line, or edge: the map becomes a planar graph, drawn without crossing lines. Colouring it means giving every vertex one of four colours, different at the two ends of each edge. Call n the number of vertices. It is enough to handle triangulations, where every face — every area enclosed by edges — is a triangle: more edges only make colouring harder.

Kempe’s swap

The basic move goes back to an 1879 paper by A. B. Kempe. Pair the four colours, say red with blue and green with yellow. A Kempe chain is a connected group of vertices wearing the two colours of one pair. Swapping those two colours along a whole chain keeps the colouring valid.

Take a vertex v with four neighbours, v0 to v3 in order around it, and colour the rest first. If the neighbours use three colours or fewer, v takes the free one. If they use all four, follow the chain that starts at v0 in the colours of v0 and v2. If it does not reach v2, swap it: v0 takes v2’s colour, freeing one for v. If it does reach v2, swap instead the chain of v1 in the colours of v1 and v3, so that v1 takes v3’s colour. This second chain cannot reach v3: the first one, running from v0 to v2 and closed through v, forms a loop that walls v1 off from v3. That is where the map being flat matters.

Pieces that can always be repaired

Proofs of the theorem rest on reducible configurations: small patterns that can be cut out, then put back once the rest is coloured. If the colours of their ring — the vertices just around them — do not fit, a bounded number of improving Kempe changes — each bringing the ring’s colours one step closer to fitting — made outside always fixes them: at most 25 for the patterns used here, whose rings have at most 18 vertices.

A reducible configuration (left; each number is how many neighbours that vertex must have in the full map) and the same pattern completed by its ring R (right). — Figure 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour and Thomas showed in 1997 how to colour this way, one pattern at a time. Each round shrinks the graph by a few vertices and costs a pass over all of it, so the time is quadratic: four times longer for a map twice as large.

In a previous paper (FOCS’26), the same six authors proved that every triangulation holds a number of non-touching reducible configurations proportional to n, taken from a list of 8,202 — or as many short loops with vertices on both sides, which also help. They remove all the patterns at once, colour the rest, then repair every ring together. A random Kempe change helps a given ring if it picks the right pairing of colours (one chance in three) and the right coin toss on every chain touching the ring (one chance in two each). With up to 18 such chains, that is at least one chance in 3 × 2¹⁸, or 786,432: small, but fixed. Each round of changes therefore helps a fixed share of the rings still waiting, and a ring needs at most 25 such helps, so the number left unrepaired shrinks by a fixed factor each time. The number of rounds thus grows only as log n, roughly the number of times n can be halved. But a single change can involve a fixed share of the whole graph, however large: each one costs a full pass, n log n in total.

A table instead of a pass

The new paper keeps the log n changes but makes each one cheaper. After a preparation taking a time proportional to n, each change is found and carried out in about n / log n steps, averaged over all the changes. The log n changes together then take a time proportional to n — linear time — a bound the authors call optimal.

The trick is the “Method of Four Russians”. A sub-problem that fits in a code of ½ log n bits — half the binary digits needed to write n — has at most √n possible versions, so all their answers can be computed in advance and stored in a table. The assumed computer, with memory words of about log n bits, reads any stored answer in one step.

The graph is cut, again and again, into nested regions with short borders. The smallest hold about log n vertices and fit, colours included, in one code. For each region, a small summary graph records which border vertices share a Kempe chain. A change then travels down as strings of “swap” or “keep” bits, and in each small region one look-up updates every colour. With about n / log n such small regions, one change costs about n / log n look-ups.

Part of a graph coloured with four colours. The grey area is a region R; thick black edges belong to the Kempe chains of the pairs red-blue and green-yellow. — Figure 2, Inoue et al. (2026), arXiv:2610.39753.

The summary of the same region: each blue blob stands for a piece of Kempe chain, and its lines show which border vertices it connects. — Figure 3, Inoue et al. (2026), arXiv:2610.39753.

Choosing without dice

With random choices, this already colours a map in linear time on average. Removing the dice without losing speed was “by far the most challenging part”. Call a ring alive while every decision so far went its way. If the u undecided chains touching it were left to coin tosses, it would survive with probability 1/2^u; summed over all live rings, these numbers give the expected number of survivors. Deciding a chain doubles the term of each ring that wanted that choice and zeroes the others. The algorithm takes the option that keeps the sum from falling, so that in the end at least as many rings are helped as chance would have helped on average.

A bound, not a stopwatch

The paper reports no implementation and no running time, and the constants hidden in “proportional to n” are not given. They are large: for each of the 8,202 patterns, the algorithm stores how many improving changes every colouring of its ring needs — “a huge constant amount of information”. In an appendix, they also fix “a minor mistake” in a 2013 construction of nested regions they build on. A conjecture from 1852 now comes with a colouring procedure whose cost grows no faster than the map it colours.