Four colours are enough for any map, so that neighbours always differ. That was proved in 1976. But how do you actually find the colours?
The classic tool is the Kempe chain. Pick two colours and take the whole connected patch of countries painted in just those two. Swap them throughout the patch: the map stays correctly coloured.
The catch: a single swap can ripple across the whole map. The previous record needed more swaps as maps grew. Each one cost a full pass over the map.
Six mathematicians, from Tokyo to Copenhagen, have removed that extra cost. Their algorithm colours n countries in a time proportional to n. Small pieces of the map are solved once, stored in tables, then simply looked up. The authors call this speed optimal.
Source: Four-Coloring Planar Graphs in Linear Time, https://arxiv.org/abs/2610.39753










