Site icon ECMI

Lyngby. Breakthrough: DTU and KU find efficient solution to famous 174-year-old mathematical headache

The Professors Carsten Thomassen, Ken-ichi Kawarabayashi, Mikkel Thorup and Bojan Mohar meeting at the University of Copenhagen, September 2026. Credit: Mikkel Thorup

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

Exit mobile version