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

Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita +3

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 ach…