We develop the first linear-time and polylogarithmic-round distributed algorithms for 5-list-coloring planar graphs and for 3-list-coloring planar graphs of girth at least five. The algorithm also extends to finding such colorings of graphs embedded in surfaces if they exist. The key ingredients are a new structure theorem for planar graphs combined with the extensive theory of hyperbolic families of graphs on surfaces.
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.
The ACO Seminar (2019–2020)