Københavns Universitet

Breakthrough: Danish researchers find efficient solution to famous 174-year-old mathematical headache

17.11.2026 11:50:37 CET | Københavns Universitet | Press release

Share

Can any map be coloured using just four colours? That is the question behind one of the most famous problems of mathematics, dating back to 1852. Since 1976, we have known that the answer is ‘yes’ – but how do you actually find the coloring? Now, two professors from the University of Copenhagen and DTU, together with international colleagues, have found the optimal algorithm after a decade-long ‘obsession’. The answer provides new fundamental mathematical insights.

Foto: Getty Images
Foto: Getty Images

For 174 years, mathematicians around the world have wrestled with the four coloring problem: Can it really be true that any map can always be coloured using no more than four colours, so that no two neighbouring regions share the same colour?

This was conjectured possible by the English mathematician Francis Guthrie in 1852, after noticing that he needed only four colours when drawing a map of the counties of England. The challenge, however, has been to prove that his conjecture always holds, regardless of what the map looks like. This is the famour Four Colour Problem that has occupied mathematicians worldwide ever since.

The first proof was presented in 1879 and stood for 11 years before an error was discovered. A full proof was finally found in 1976, so now we had a four colour theorem, but the proof was controversial because it relied heavily on computer calculations that other mathematicians found difficult to verify. 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, an international team of mathematicians, including two Danish professors, has achieved the first major breakthrough in 30 years: they have found the optimal algorithm to efficiently four-colour any map.

“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.

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.

1,000 mathematicians struck by the disease

Mikkel Thorup and his research colleagues, including Carsten Thomassen, Ken-ichi Kawarabayashi and Bojan Mohar, have worked on the Four Colour Problem for around ten years. Thorup calls it “the four-colour disease”:

“The disease is believing that there must be a simple proof for such a simple statement. I would guess that at least 1,000 mathematicians have caught the four-colour disease, spending months trying to make it work but never quite succeeding. It is the disease people have suffered from since 1852.”

But why would anyone spend years working on a thing like this, you might wonder.

“Because mathematicians are slightly crazy. Most of what mathematicians work on consists of very nerdy questions. We become obsessed with this type of problem because it challenges the human intellect. And if we find the answer, we'll probably also find answers to other mathematical puzzles," says Mikkel Thorup.

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

Built on new mathematical insight

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.

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 call quadratic 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.

Relevant to swim rings and emmental cheese too

With the new breakthrough, the researchers have done more than just find a faster way to colour maps. Their new insight into the structure of graphs extends beyond the classical Four Colour Problem and opens up new possibilities for studying far more complex types of graphs and surfaces.

“The remarkable thing is that because there are so many handles, the idea can also be applied to other kinds of surfaces besides a flat map. For example, surfaces with holes, such as a swim ring or a piece of Emmental cheese. That is why we believe the result could have significance far beyond the Four Colour Theorem,” says Mikkel Thorup.

PhD students and co-authors Yuta Inoue and Atsuyuki Miyashita, University of Tokyo. Credit: University of Tokyo


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.

THE FOUR COLOUR PROBLEM

  • The Four Colour Problem was formulated by Francis Guthrie in 1852 and is now regarded as one of the most famous and most extensively studied problems in mathematics.

  • The problem asks whether any map can be coloured using at most four colours so that no neighbouring countries or regions share the same colour.

  • The first claimed proof was published in 1879 by Alfred Kempe but was later shown to contain an error.

  • In 1976, Kenneth Appel and Wolfgang Haken produced the first correct proof. It was the first major mathematical proof to rely substantially on computer calculations.

  • The proof sparked debate because no mathematician could manually verify all the thousands of computer checks it involved.

  • In 1996, Robertson, Sanders, Seymour and Thomas produced a more accessible proof, which also provided the best algorithm available at the time. However, it was a quadratic algorithm, meaning it becomes much slower as the graph grows.

  • The new 2026 algorithm is an optimal linear algorithm, with running time increasing at the same rate as the size of the graph. It is the first major algorithmic improvement to the Four Colour Problem in 30 years.

Keywords

Contacts

Mikkel Thorup
Professor
Department of Computer Science
University of Copenhagen
mthorup@di.ku.dk
+45 35 33 57 10/+45 21 17 91 23

Maria Hornbek
Communications Officer
UCPH Communication
University of Copenhagen
maho@adm.ku.dk
+45 22 95 42 83

Images

The Professors Carsten Thomassen, Ken-ichi Kawarabayashi, Mikkel Thorup and Bojan Mohar meeting at the University of Copenhagen, September 2026.
The Professors Carsten Thomassen, Ken-ichi Kawarabayashi, Mikkel Thorup and Bojan Mohar meeting at the University of Copenhagen, September 2026.
Credit: Mikkel Thorup
Download
PhD students and co-authors Yuta Inoue and Atsuyuki Miyashita, University of Tokyo.
PhD students and co-authors Yuta Inoue and Atsuyuki Miyashita, University of Tokyo.
Credit: University of Tokyo
Download

Links

About the University of Copenhagen

The University of Copenhagen was founded in 1479 and today has 37,000 students and 10,000 employees – of whom more than 5,000 are researchers – and revenues of DKK 11.3 billion.

10 Nobel Prizes have been awarded to researchers at the University.

Subscribe to releases from Københavns Universitet

Subscribe to all the latest releases from Københavns Universitet by registering your e-mail address below. You can unsubscribe at any time.

Latest releases from Københavns Universitet

Gennembrud: Danske forskere har fundet en effektiv løsning på 174 år gammel matematisk hovedpine17.11.2026 10:58:34 CET | Pressemeddelelse

Kan ethvert landkort farvelægges med blot fire farver? Det handler et af matematikkens mest berømte problemer om, som stammer fra 1852. Vi har siden 1976 vidst at svaret er 'ja', men hvordan gør man det? Nu har to professorer fra Københavns Universitet og DTU sammen med udenlandske kolleger fundet en optimal algoritme, og det efter 10 års ’besættelse’. Svaret giver nye grundlæggende matematiske indsigter.

High water, high rents: Poorest residents pay the most for climate adaptation12.11.2026 07:17:00 CET | Press release

As cities worldwide adapt to extreme weather, climate adaptation must prevent people from wading through flooded streets in the future. But the costs are not equally shared. A study from the University of Copenhagen shows that climate adaptation policies may even make social inequality worse. In Copenhagen, stormwater costs fall disproportionately on not-for-profit housing residents, as these neighborhoods are often located near climate adaptation projects.

In our pressroom you can read all our latest releases, find our press contacts, images, documents and other relevant information about us.

Visit our pressroom
World GlobeA line styled icon from Orion Icon Library.HiddenA line styled icon from Orion Icon Library.Eye