PIMS/SFU Discrete Math Seminar: Bojan Mohar

Abstract:

In 1992, Thomassen obtained a beautiful proof showing that every planar graphis 5-list-colorable. Some extensions of this result will be presented. Inparticular, a new proof of Thomassen's theorem will be outlined. This proof is unnecessarily complicated but it provides a powerful new approach. It will be explained how to use it to prove that
every graph drawn in the plane so that the distance between every pair of crossings is at least 19 is 5-list-colorable. At the same time we may allow some vertices to have lists of size four only, as long as they are far apart and far from the crossings. This is joint work with Zdenek
Dvorak and Bernard Lidicky.