Discrete Mathematics and Optimization Seminar

University of Toronto
Monday September 20th at 4.30pm
Burnside 1205

Title. Choosability of Planar Graphs without Cycles of Specific Lengths.

Abstract. 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.