A proof of a conjecture of Ohba

A list colouring problem asks the following: given an assignment of lists L(v) of colours to each vertex v of a graph G, does there exist a proper colouring f of G such that f(v) ∈ L(v) for every vertex v? Such a colouring is called an acceptable colouring for L. The list chromatic number of G, denoted χ`(G), is defined to be the minimum k such thatG has an acceptable L-colouring whenever |L(v) | ≥ k for all v ∈ V (G). Of course, a proper k-colouring of G is equivalent to an acceptable colouring for L where L(v) = {1, 2,..., k} for all v ∈ V (G). Therefore, we have the following bound: χ ≤ χ`. List colouring was introduced independently by Vizing [7] and Erdős et al. [1] and has become a popular topic among researchers (see e.g. [8]). Of particular interest is the problem of determining classes of graphs which satisfy χ ` = χ. These graphs are said to be chromatic-choosable [3]. In this paper, we prove the following conjecture of Ohba [3]. Conjecture 1 (Ohba [3]). If |V (G) | ≤ 2χ(G) + 1, then G is chromatic