Online Talk: Evelyne Smith-Roberge

Tuesday, Sept 14, 3pm ET (8pm BST, 7am Wed NZST)
Evelyne Smith-Roberge, University of Waterloo
A local choosability theorem for planar graphs

Two famous theorems of Thomassen show that every planar graph is 5-choosable, and that every planar graph of girth at least five is 3-choosable. These theorems are best possible for uniform list assignments: Voigt gave a construction of a planar graph that is not 4-choosable, and of a planar graph of girth four that is not 3-choosable. In this talk, I will introduce the concept of a local girth list assignment: a list assignment wherein the list size of each vertex depends not on the girth of the graph, but only on the length of the shortest cycle in which the vertex itself is contained. I will present a local choosability theorem for planar graphs that unifies the two theorems of Thomassen mentioned above. Joint work with Luke Postle.


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.