The Four Color Theorem with Linearly Many Reducible Configurations and Linear Time Coloring
- Prof. Mikkel Thorup, University of Copenhagen
- Time: 2026-12-02 15:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
We present a linear time 4-coloring algorithm for planar graphs, improving on the previous quadratic time algorithm by Robertson et al. from 1996. Such an algorithm cannot be achieved by the known proofs of the Four Color Theorem (4CT) which only show the existence of a reducible configuration. We show that every planar triangulation contains linearly many pairwise non-touching reducible configurations or obstructing cycles of length at most 5 (which all allow for making effective 4-coloring reductions). Based on this we present a simple O(n log n) algorithm to 4-color any planar graph. The running time of the 4-coloring is reduced to linear using new data structures.
Biography
Mikkel Thorup (born 1965) has a D.Phil. from Oxford University from 1993. From 1993 to 1998 he was at the University of Copenhagen. From 1998 to 2013 he was at AT&T Labs-Research. Since 2013 he has been back as Professor at the University of Copenhagen. He is currently a VILLUM Investigator heading Center for Basic Algorithms Research Copenhagen (BARC)
Mikkel is a Fellow of the ACM, a Fellow of AT&T, and a Member of the Royal Danish Academy of Sciences and Letters. He is co-winner of the 2011 MAA Robbins Award in mathematics and winner of the 2015 Villum Kann Rasmussen Award for Technical and Scientific Research, which is Denmark's biggest individual prize for research. He was co-winner of the 2021 AMS-MOS Fulkerson Prize and the 2021 ACM STOC 20-year test of time award. He is also co-winner of the FOCS'26 Best Paper Award for a fast algorithm to 4-color planar graphs.
Mikkel's main work is in algorithms and data structures, where he has worked on both upper and lower bounds. Recently one of his main focusses has been on hash functions unifying theory and practice. Mikkel prefers to seek his mathematical inspiration in nature, combining the quest with his hobbies of bird watching and mushroom picking.
Finally some numbers: H-index above 70 (Google Scholar). More than 200 publications with more than 100 in topmost venues (A* in CORE ranking). This includes more than 50 papers at the topmost general theory of computing conferences STOC and FOCS, and more than 30 papers at the topmost algorithms conference SODA. Erdős number 2.