Jump To中央區塊/Main Content :::
:::

Seminars

Colloquium

The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring

2026/12/07 (Mon.) 15:30~16:30
  • Date : 2026/12/07 (Mon.) 15:30~16:30
  • Location : Seminar Room 638, Institute of Mathematics (NTU Campus)
  • Speaker : Mikkel Thorup (University of Copenhagen)
  • Abstract :
    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.
:::