The Four Color Theorem Now Runs in Near-Linear Time — First Improvement in 30 Years
A new paper by Kawarabayashi, Thorup, Mohar, and Thomassen gives an O(n log n) algorithm for 4-coloring planar graphs, breaking a 30-year quadratic barrier.
A new paper by Kawarabayashi, Thorup, Mohar, and Thomassen gives an O(n log n) algorithm for 4-coloring planar graphs, breaking a 30-year quadratic barrier.