Description
This is a joint BBC+G/Combinatorics seminar
We give a near-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 pairwise non-crossing 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.