In a recent arXiv paper, Inoue, Kawarabayashi, Miyashita, Mohar, Thomassen, and Thorup (Inoue et al. 2026) presented a near-optimal algorithm that computes a four-colouring of an -vertex planar graph in time. This resolves a long-standing algorithmic problem: while the existence of a four-colouring for planar graphs has been known for decades, obtaining such a colouring in near-linear time had remained open.
Few questions in graph theory have a history as rich and influential as the four-colour problem. First posed by Francis Guthrie in 1852, it asks whether the regions of any map can always be coloured with at most four colours in such a way that any two regions sharing a common boundary segment receive different colours. This problem admits a natural graph-theoretic formulation. Given a map, one places a vertex in each region and joins two vertices by an edge whenever the corresponding regions are adjacent. In this way one obtains a graph that can be drawn in the plane so that edges intersect only at their endpoints. Such a graph is called planar. The map-colouring question is therefore equivalent to asking whether every planar graph has chromatic number at most .
The four-colour problem shaped the development of modern graph theory and topological methods for more than a century. Its eventual resolution by Appel and Haken (Appel and Haken 1977; Appel et al. 1977) was a landmark event: they proved that every planar graph is indeed four-colourable, thereby establishing the Four Colour Theorem. Their proof was also historically significant because it was one of the first major theorems to rely heavily on computer verification, sparking extensive discussion about the nature of proof in mathematics.
From an algorithmic perspective, however, the theorem does not by itself provide an efficient method for producing a four-colouring of a given planar graph. This challenge was addressed in 1996 by Robertson, Sanders, Seymour, and Thomas (Robertson et al. 1996), who gave the first polynomial-time algorithm that actually constructs a four-colouring of any -vertex planar graph in time. Their work showed that the Four Colour Theorem could be made constructive in a strong computational sense, but it still left open the possibility of substantially faster algorithms.
The advance of Inoue et al. (Inoue et al. 2026) closes much of this gap. Their algorithm is near-optimal, since planar graphs have only edges, and thus merely reading the input already requires linear time. Achieving a running time within a logarithmic factor of this lower bound is therefore essentially best possible with current input models. Beyond its technical sophistication, the result is important because it transforms a classical existence theorem into an almost optimally efficient algorithmic procedure. It is a striking example of how a problem rooted in nineteenth-century mathematics continues to inspire new ideas at the forefront of contemporary graph algorithms.