Title: Canvases and Colouring
Speaker: | Luke Postle |
Affiliation: | University of Waterloo |
Room: | MC 5417 |
Abstract: In 1994, Thomassen proved that every plane graph G is 5-choosable by proving a stronger statement, namely that if vertices in the interior have lists of size 5 and the vertices on the outer face have lists of size 3 except for two adjacent vertices on the outer face which are precoloured, then G has an colouring from those lists. Let us say that, in the statement above, the lists of the outer face have been restricted. Here we outline the proof of a far reaching generalization of his result: there exists a D>0 such that if G is a plane graph and F is a set of faces, pairwise at least distance D apart, and L is a list assignment where only the faces of F are restricted, then G has an L-colouring. Joint work with Robin Thomas.