Towards an on-line version of Ohba’s conjecture

The on-line choice number of a graph is a variation of the choice number defined through a two person game. It is at least as large as the choice number for all graphs and is strictly larger for some graphs. In particular, there are graphs G with | V ( G ) | = 2 χ ( G ) + 1 whose on-line choice numbers are larger than their chromatic numbers, in contrast to a recently confirmed conjecture of Ohba that every graph G with | V ( G ) | ⩽ 2 χ ( G ) + 1 has its choice number equal to its chromatic number. Nevertheless, an on-line version of Ohba’s conjecture was proposed in [P. Huang, T. Wong and X. Zhu, Application of polynomial method to on-line colouring of graphs, European J. Combin., 2011]: every graph G with | V ( G ) | ⩽ 2 χ ( G ) has its on-line choice number equal to its chromatic number. This paper confirms the on-line version of Ohba’s conjecture for graphs G with independence number at most 3 . We also study list colouring of complete multipartite graphs K 3 ⋆ k with all parts of size 3 . We prove that the on-line choice number of K 3 ⋆ k is at most 3 2 k and present an alternate proof of Kierstead’s result that its choice number is ⌈ ( 4 k − 1 ) / 3 ⌉ . For general graphs G , we prove that if | V ( G ) | ⩽ χ ( G ) + χ ( G ) then its on-line choice number equals the chromatic number.