|Discrete Mathematics and Optimization Seminar
University of Toronto
Monday September 20th at 4.30pm
Title. Choosability of Planar Graphs without Cycles of Specific Lengths.
An L-colouring of a graph G is a vertex colouring
in which every vertex gets a colour from a list L(v) of allowed colours.
G is called l-choosable if G is L-colourable for all
possible assignments L in which all lists L(v) have l-colours.
Let k be an integer, 3<= k <=6. Other known results imply that
if G is a planar graph with no cycle
of length k, then G is 4-choosable.
We use the discharging method to prove the conjecture that if G is a
planar graph without 7-cycles, then G is 4-choosable.