Ohba’s conjecture is true for graphs with independence number at most three

AbstractA graph G is said to be chromatic-choosable if its choice number is equal to its chromatic number. Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. At present, only several special classes of graphs have been verified, for which Ohba’s conjecture is true. In 2004, Ohba proved that if |V(G)|≤2χ(G) and the independence number of G is at most 3, then G is chromatic-choosable (Ars Combinatoria, 72 (2004), 133–139). In this work we show that if |V(G)|≤2χ(G)+1 and the independence number of G is at most 3, then G is chromatic-choosable. This proves that Ohba’s conjecture is true for all graphs G with independence number at most 3 and all χ(G)-chromatic subgraphs of G