Graphs and Matroids Seminar - Matt Kroeker

Title: List Colouring and Ohba's Conjecture

Abstract:

The question of when the list-chromatic number of a graph G, denoted chi_l(G), equals its chromatic number is fundamental to the theory of list colouring. In their original paper on the subject, Erdős, Rubin and Taylor showed that chi_l(G) = chi(G) if G is a complete multipartite graph with parts of size at most two. Ohba later conjectured a broad generalization of this result, namely that chi_l(G) = chi(G) if |V(G)| <=  2chi(G) +1, which was proved by Noel, Reed and Wu in 2014. This talk will survey various list colouring techniques surrounding this problem, with particular emphasis on the proof of a generalization due to Noel, West, Wu and Zhu.