Choosability of Graphs with Bounded Order

Jonathan Noel

McGill

Abstract

The choice number of a graph, denoted ch(G), is defined as the minimum integer k such that, for any assignment of lists of size k to the vertices of G, there is a proper colouring in which every vertex is mapped to a colour in its list.

It is clear that the choice number is at least as large as the chromatic number, but the converse is far from true. As observed by Erdos, Rubin and Taylor, the choice number is not bounded above by any real-valued function of the chromatic number.

One of the central problems in graph colouring is to determine conditions under which the choice number is bounded in terms of the chromatic number. In this talk, we discuss the proof of a conjecture of Ohba, which says that if the number of vertices is at most twice the chromatic number plus one, then the choice number and the chromatic number are equal. We also discuss some recently proved generalizations of Ohba's Conjecture, and