A six-author team — Inoue, Kawarabayashi, Miyashita, Mohar, Thomassen and Thorup — has published "The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring" (arXiv:2603.24880), which won Best Paper at FOCS 2026 in New York (8–11 November 2026). It is the first major efficiency breakthrough for four-colouring in about thirty years: colouring a planar map went from quadratic time O(n²) to near-linear O(n log n). A follow-up paper in October 2026 (arXiv:2610.39753) reaches optimal linear time O(n).
Key facts
| Item | Details |
|---|---|
| Paper | "The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring" |
| arXiv | 2603.24880 |
| Authors | Inoue, Kawarabayashi, Miyashita, Mohar, Thomassen, Thorup |
| Award | Best Paper, FOCS 2026 (8–11 November 2026, New York) |
| Before | Quadratic time O(n²) |
| After | Near-linear time O(n log n) |
| Follow-up (October 2026) | Optimal linear time O(n) — arXiv:2610.39753 |
| Unavoidable set | 8,202 configurations |
| Project began | 2015 |
| Featured | Quanta Magazine, September 2026 |
What this means / what to watch
The key insight is that planar graphs contain linearly many reducible configurations; the unavoidable set used has 8,202 configurations. The work matters beyond pure maths: the techniques for finding reducible configurations efficiently apply to other graph problems, including scheduling and register allocation in compilers. The project began in 2015 and was featured in Quanta Magazine in September 2026.
A note on verification
The facts in this post are verified from the sources named in our research file (phys.org, 18 November 2026; NII / brightsurf; BARC Copenhagen; arXiv, both papers; SFU, Mohar page; Quanta Magazine), with each fact confirmed by two or more sources.
FAQs
What did the paper actually improve?
The efficiency of colouring: colouring a planar map went from quadratic time O(n²) to near-linear time O(n log n). It is the first major efficiency breakthrough for four-colouring in about thirty years.
What is the key insight?
Planar graphs contain linearly many reducible configurations. The unavoidable set used has 8,202 configurations.
What does the follow-up paper add?
A follow-up paper in October 2026 (arXiv:2610.39753) reaches optimal linear time O(n).
Why does this matter beyond pure maths?
The techniques for finding reducible configurations efficiently apply to other graph problems, including scheduling and register allocation in compilers.
Source: phys.org (18 Nov 2026); NII / brightsurf; BARC Copenhagen; arXiv (both papers); SFU (Mohar page); Quanta Magazine. Last checked: 21 November 2026.
Comments (0)
Share your question or experience about this syllabus. Your comment will appear after review.
No comments yet — be the first to share your thoughts!