Can any map be coloured using just four colours so that no two neighbouring regions share the same colour? The question from 1852 is one of the world’s most famous problems in mathematics. The answer is yes and came in 1976. In 1997, a new and more accessible proof was introduced. It could also find a four-colouring, but algorithmically it was slow when applied to large maps. Now, two professors from DTU Compute and the University of Copenhagen (KU), together with international colleagues, have found the most efficient algorithm to date for four-colouring any map, after a decade-long ‘obsession’. The answer provides new fundamental mathematical insights.
(Photo: The Professors from left, Carsten Thomassen, Ken-ichi Kawarabayashi, Mikkel Thorup and Bojan Mohar meeting at the University of Copenhagen, September 2026. Credit: Mikkel Thorup)
“The previous proofs showed that it is always possible to colour a map using four colours. But they are not very good at actually finding the colours for each individual region on a map. The new algorithm is efficient and provides a much faster way of colouring,” says Professor Mikkel Thorup from the Department of Computer Science at the University of Copenhagen, one of the researchers behind the study in a press release.
The first paper about the research has just been presented at one of the world’s leading conferences in theoretical computer science, FOCS’26, where it received the Best Paper Award.
The reason the new algorithm is far more efficient than previous ones is that it is based on an entirely new mathematical insight discovered by the research team.
In mathematical language, a surface such as a map is called a planar graph. The researchers have discovered that graphs contain far more so-called reducible configurations than previously believed. These are small sections of a graph that give mathematicians a place to start when working out a colouring.
“Think of reducible configurations as handles you can grab hold on to start four colouring. We show that graphs do not contain just one handle, but an astonishing number of them. Nobody knew that before,” says Professor and co-author Carsten Thomassen from DTU Compute.
Because the researchers can now find “handles” in many places across a graph, whereas previously they could often find only a single one, they can begin the colouring process from many different locations and therefore colour even very large maps much more quickly.
“We have gone from what mathematicians callquadratic time to linear time. This means that if a map contains ten times as many regions, the computation only becomes about ten times slower. With the previous algorithm, it would have become about 100 times slower,” explains Carsten Thomassen.
Their new insight into the structure of graphs opens new possibilities for studying, for example, surfaces with holes, such as a swim ring or a piece of Emmental cheese.
Read the full story at DTU Compute and the press release (author Maria Hornbek) from the University of Copenhagen
ABOUT THE STUDY
- In addition to Mikkel Thorup from the University of Copenhagen and Carsten Thomassen from DTU, the following researchers contributed to the result: Ken-ichi Kawarabayashi from the National Institute of Informatics in Tokyo; Bojan Mohar from Simon Fraser University; and Yuta Inoue and Atsuyuki Miyashita from the University of Tokyo. Following mathematical tradition, all authors are considered equal contributors.
- The research paper The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring was selected for FOCS 2026 (IEEE Symposium on Foundations of Computer Science), one of the world’s leading conferences in theoretical computer science, and received the conference’s Best Paper Award.
- Shortly after the FOCS paper was published, the researchers released a follow-up paper, Four-Coloring Planar Graphs in Linear Time, demonstrating that the Four Colour Problem can be solved not merely in near-linear time, but in optimal linear time.
