PIMS/SFU Discrete Math Seminar: Bojan Mohar
- Date: 12/06/2011
- Time: 14:30
Lecturer(s):
Bojan Mohar
Location:
Simon Fraser University
Topic:
5-choosability of graphs with crossings
Description:
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 thatevery 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 ZdenekDvorak and Bernard Lidicky.
Other Information:
Sponsor:
