BARC paper on the Four Color Theorem receives Best Paper Award at FOCS’26
A paper co-authored by BARC head Mikkel Thorup, “The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring” (preprint), will receive the Best Paper Award at the 2026 IEEE Symposium on Foundations of Computer Science (FOCS) in November. The paper is joint work with Yuta Inoue and Atsuyuki Miyashita (University of Tokyo), Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo), Bojan Mohar (Simon Fraser University), and Carsten Thomassen (Technical University of Denmark).
The Four Color Theorem is one of the most famous results in mathematics, and one of the simplest to state: the regions of any map can be colored with four colors so that no two neighbouring regions share a color. Posed in 1852, it resisted proof for well over a century. A proof announced in 1879 stood for eleven years before a flaw was found, and the theorem was only settled in 1976 by Appel and Haken, who reduced the problem to checking 1,482 “unavoidable configurations” by computer. At the time this was controversial, as it was the first major theorem whose proof could not be verified by hand. A streamlined computer proof by Robertson, Sanders, Seymour and Thomas in 1997 brought the number of configurations down to 633 and gave an algorithm that four-colors any planar graph with n vertices in roughly n² steps.
The new paper gives a third computer-assisted proof, and the first with an algorithmic payoff: a four-coloring can now be found in near-linear time, O(n log n). The key new idea is to look for reducible configurations in the “flat” regions of a planar graph. The flat parts can be thought of as areas where the average degree is exactly 6 and not strictly below 6 as guaranteed by Euler's formula from 1758. No previous proof could find reducible configurations in these flat parts. But flat regions make up most of a large planar graph, and using them, the authors show that any planar graph contains a linear number of reducible configurations. The many reducible configurations allow them to 4-color planar graphs much more efficiently. The resulting unavoidable set has 8,202 configurations and took hours of computing time to verify. Along the way, the work uncovers new structural properties of planar graphs that the authors are now applying to coloring problems on other surfaces.
The project began in 2015 with a conversation between Thorup and Kawarabayashi on the beach in Nyborg, and took almost a decade to complete. The result was featured in Quanta Magazine in September.
Recently the authors showed that the 4-coloring can be done in linear time, which is optimal https://arxiv.org/abs/2610.39753. The improvement from near-linear to linear time is based on new data structures.
Other BARC papers at FOCS’26
FOCS, a leading conference in algorithms and complexity, will be held in New York City on November 8–11. In addition to the papers above, the following papers co-authored by BARC researchers will be presented:
Branch-width of connectivity functions is fixed-parameter tractable. Tuukka Korhonen, Sang-il Oum.
Connectivity augmentation is fixed-parameter tractable. Tuukka Korhonen, Mikkel Thorup.
Derandomized Sunflowers and Radical Lower Bounds. Bruno Pasqualotto Cavalar, Théo Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff.
Hard CNF Instances for Ideal Proof Systems: The ROABP Case. Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret.
Instance-Optimality of Bidirectional PageRank Estimation. Mikkel Thorup, Hanzhi Wang.
Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size. Susanna F. de Rezende, David Engström, Yassine Ghannane, Kilian Risse.
Papers by visiting researchers
BARC is also pleased that two of this year’s visitors have papers at FOCS’26. Huacheng Yu, who is visiting BARC on sabbatical from Princeton University, has three papers, all in the area of streaming and communication complexity:
Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams. Cheng Jiang, Yinchen Liu, Huacheng Yu.
Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streams. Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou.
Gap-Majority Lemmas in Communication Complexity. Pachara Sawettamalya, Huacheng Yu.
Visiting researcher Noel Arteche from Lund University has a paper in proof complexity:
The Proof Analysis Problem for Constant-Depth Frege. Noel Arteche, Susanna F. de Rezende, Erfan Khaniki, Kilian Risse.