19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

5-choosability of graphs with crossings far apart

Presented by Mr. Zdenek DVORAK
Type: Oral presentation
Track: Coloring of Graphs


We give a new proof of the fact that every planar graph is 5-choosable, and use it to show that every graph drawn in the plane so that the distance between every pair of crossings is at least 19 is 5-choosable. 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.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors