Speaker
Description
The Four-Color Theorem had profound influence on the developments of graph theory. It was proved 49 years ago by Appel and Haken. However, its proof left many questions unanswered. Is this result just a coincidence, or are there deeper reasons behind it? We try to provide deeper understanding why the 4CT is true. The speaker will give an overview of recent breakthrough results obtained in collaboration with Ken-ichi Kawarabayashi, Carsten Thomassen, Mikkel Thorup, Yuta Inoue, Atsuyuki Miyashita, and Tomohiro Sonobe.
The main results are based on a strengthening of the 4CT that includes the "flat curvature" analysis, which in particular leads to optimized algorithms for 4-coloring planar graphs. Moreover, it gives way towards resolutions of old conjectures of Grunbaum (1969), Albertson (1981), and Robertson (1994), and also gives a strong version of the Tutte 4-flow conjecture for graphs of small Euler genus.
