Gennembrud: Danske forskere har fundet en effektiv løsning på 174 år gammel matematisk hovedpine
17.11.2026 10:58:34 CET | Københavns Universitet | 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.

I 174 år har matematikere verden over bakset med det. Kan det virkelig passe, at man altid kan farvelægge ethvert landkort med højst fire farver, så ingen lande, der grænser op mod hinanden, har samme farve?
Det påstod den engelske matematiker Francis Guthrie i 1852 efter at have erfaret, at han kun behøvede fire farver, da han lavede et kort over engelske grevskaber. Problemet har bare været at bevise, at hans påstand altid holder, uanset hvordan landkortet ser ud. Påstanden kaldes Firefarve-problemet og har optaget matematikere over hele verden lige siden.
Første bevis blev fremlagt i 1879 og holdt i 11 år, før man opdagede en fejl. I 1976 kom et fuldt bevis, men som var kontroversielt, blandt andet fordi det byggede på omfattende computerberegninger, som andre matematikere havde svært ved at efterprøve. I 1997 kom et nyt og mere overskueligt bevis, der også kunne finde en firefarvning, men som algoritmisk var langsomt, hvis man skulle farvelægge store landkort.
Nu har et internationalt hold af matematikere med to danske professorer gjort det første gennembrud i 30 år: De har fundet den optimale algoritme, der kan firefarve ethvert landkort effektivt.
”De tidligere beviser viste godt nok, at det altid er muligt at farvelægge et landkort med fire farver. Men de er ikke gode til rent faktisk at finde frem til farverne for hvert enkelt landområde på et kort. Den nye algoritme er effektiv og giver en langt hurtigere måde at farvelægge på,” siger professor Mikkel Thorup fra Datalogisk Institut på Københavns Universitet, der er en af forskerne bag studiet.
Første forskningsartikel om arbejdet er netop blevet præsenteret på en af verdens førende konferencer inden for teoretisk datalogi, FOCS, hvor den har vundet prisen for årets bedste forskningsartikel.
1000 matematikere ramt af sygdom
Mikkel Thorup og forskerkollegerne, der bl.a. tæller Carsten Thomassen, Ken-ichi Kawarabayashi og Bojan Mohar, har arbejdet med firefarveproblemet i cirka 10 år. Mikkel Thorup kalder det ’firefarve-sygdommen’:
”Sygdommen er, at man tænker, at der må findes et simpelt bevis på så simpel en påstand. Og jeg skyder på, at der dags dato er mindst 1000 matematikere, der har haft firefarve-sygdommen, hvor man prøver i månedsvis, men simpelthen ikke kan få det til at passe sammen. Det er den sygdom, folk har haft siden 1852.”
Men hvorfor gider voksne mennesker i det hele taget beskæftige sig med dette her problem år ind og år ud, kan man tænke.
”Det er fordi matematikere er skrupskøre. Det meste, matematikere arbejder med, er jo ekstremt nørdede spørgsmål. Vi bliver besat af denne type spørgsmål, fordi det er en udfordring for det menneskelige intellekt. Det handler også om, at hvis vi finder svaret, finder vi sikkert også svaret på nogle andre matematiske gåder,” siger Mikkel Thorup.

Bygger på ny matematisk indsigt
Grunden til at den nye algoritme er meget mere effektiv end de tidligere, er, at den bygger på en helt ny matematisk indsigt, som forskerholdet har opnået.
I matematisk sprog kaldes en overflade som et landkort for en planær graf. Forskerne har fundet ud af, at grafer indeholder langt flere såkaldte reducerbare konfigurationer, end man hidtil har troet. Det er små udsnit af grafen, som giver matematikere et sted at tage fat, når de skal finde frem til farvelægningen.
”Tænk på reducerbare konfigurationer som håndtag, man kan gribe fat i for at komme i gang med at farvelægge grafen. Vi viser, at der ikke bare findes ét, men ufatteligt mange håndtag i grafer. Og det var der ingen, der vidste før,” siger professor og medforfatter Carsten Thomassen fra DTU.
Fordi forskerne nu kan finde ’håndtag’ mange steder i grafen, hvor man hidtil kun kunne finde et enkelt, kan de begynde farvelægningen mange steder og dermed farve selv meget store kort meget hurtigere.
”Vi er gået fra en hastighed, der i matematikken hedder kvadratisk tid, til lineær tid. Det betyder, at selv om et landkort bliver 10 gange større, bliver beregningen kun omkring 10 gange langsommere – hvor den med den tidligere algoritme ville blive omkring 100 gange langsommere,” forklarer Carsten Thomassen.
Gælder også bildæk og emmentalere
Med det nye gennembrud har forskerne ikke blot fundet en hurtigere metode til at farvelægge landkort. Den nye indsigt i grafers opbygning rækker ud over det klassiske firefarveproblem. Den giver nye muligheder for at studere langt mere komplicerede typer af grafer og overflader.
”Det er faktisk sådan, at fordi der er så mange håndtag, vil idéen også kunne bruges, når man ser på andre typer overflader end et fladt landkort. Det kunne for eksempel være overflader med huller som et bildæk eller en emmentaler-ost. Derfor tror vi, at resultatet kan få betydning langt ud over firefarve-problemet,” siger Mikkel Thorup.

OM STUDIET
- Udover Mikkel Thorup fra KU og Carsten Thomassen fra DTU har følgende bidraget til forskningsresultatet: Ken-ichi Kawarabayashi fra National Institute of Informatics i Tokyo; Bojan Mohar fra Simon Fraser University samt Yuta Inoue og Atsuyuki Miyashita fra University of Tokyo. I matematisk tradition er alle forfattere ligestillet.
- Forskningsartiklen The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring blev udvalgt til FOCS 2026 (IEEE Symposium on Foundations of Computer Science), en af verdens førende konferencer inden for teoretisk datalogi og har modtaget konferencens pris for bedste forskningsartikel.
- Kort efter FOCS-artiklen offentliggjorde forskerne et opfølgende arbejde, Four-Coloring Planar Graphs in Linear Time, som viser, at firfarveproblemet ikke blot kan løses i nær-lineær tid, men i lineær tid, hvad der er optimalt.
DET STORE FIREFARVE-PROBLEM
- Firefarveproblemet blev formuleret af Francis Guthrie i 1852 og regnes i dag blandt matematikkens mest berømte og mest studerede problemer.
- Problemet spørger, om ethvert landkort kan farvelægges med højst fire farver, så ingen nabolande får samme farve.
- Det første påståede bevis blev offentliggjort i 1879 af Alfred Kempe, men viste sig senere at indeholde en fejl.
- I 1976 leverede Kenneth Appel og Wolfgang Haken det første korrekte bevis. Det var det første store matematiske bevis, der i betydelig grad byggede på computerberegninger.
- Beviset skabte debat, fordi ingen matematikere kunne gennemgå alle de tusindvis af computerkontroller manuelt.
- I 1996 kom et mere overskueligt bevis fra Robertson, Sanders, Seymour og Thomas, som samtidig gav den tidligere bedste, men kvadratiske, algoritme til problemet.
- Det nye arbejde med en optimal linær algoritme i 2026 er således den første store algoritmiske forbedring af firefarveproblemet i 30 år.
Nøgleord
Kontakter
Mikkel Thorup
Professor
Datalogisk Institut
Københavns Universitet
mthorup@di.ku.dk
35 33 57 10 / 21 17 91 23
Maria Hornbek
Kommunikationskonsulent
KU Kommunikation
Københavns Universitet
maho@adm.ku.dk
22 95 42 83
Billeder


Om Københavns Universitet
Københavns Universitet blev grundlagt i 1479 og har i dag cirka 37.000 studerende og 10.000 ansatte – heraf flere end 5.000 forskere – og en omsætning på 9,4 milliarder kroner. 10 nobelpriser er blevet tildelt forskere med tilknytning til universitetet.
Følg pressemeddelelser fra Københavns Universitet
Skriv dig op her, og modtag pressemeddelelser på e-mail. Indtast din e-mail, klik på abonner, og følg instruktionerne i den udsendte e-mail.
Flere pressemeddelelser fra Københavns Universitet
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.
Højere vandstand, højere husleje: Klimasikring kan koste de fattigste mest12.11.2026 07:16:00 CET | Pressemeddelelse
Klimasikring skal forhindre, at københavnerne vader gennem oversvømmede gader i fremtiden. Men regningen er ikke fordelt lige mellem dem. Borgere i almene boliger kan komme til at betale den største del, viser forskning fra Københavns Universitet.
Kaffe ser ud til at ændre, hvordan din tarm fungerer10.11.2026 10:22:45 CET | Pressemeddelelse
Drikker du kaffe hyppigt, lader det til at ændre dine tarmbakterier, men også selve din tarms fysiologi. Det er resultatet af et studie fra Københavns Universitet, som måske kan pege i retning af, hvordan vi bedre afhjælper forstoppelse.
Coffee appears to change how your gut functions10.11.2026 10:20:38 CET | Press release
If you drink coffee regularly, it appears to alter not only your gut bacteria but also the physiology of the gut itself. That is the conclusion of a study from the University of Copenhagen, which may help point the way towards better treatments for constipation.
Luftforurening tidligt i livet kan spores i lungerne helt op i ungdomsårene9.11.2026 06:55:00 CET | Pressemeddelelse
På trods af en forbedret luftkvalitet i Danmark finder et nyt studie en sammenhæng mellem luftforurening tidligt i livet og børn og unges lungefunktion. Selv små forskydninger kan have stor betydning for befolkningens sundhed, siger forsker.
I vores nyhedsrum kan du læse alle vores pressemeddelelser, tilgå materiale i form af billeder og dokumenter samt finde vores kontaktoplysninger.
Besøg vores nyhedsrum