2011/11/23 by Jakub Kozik, Kozik, Jakub, Piotr Micek +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1111.5458
new abstract and introduction
arxiv created 2012/12/06 · arxiv updated 2012/12/07
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 its chromatic number. Nevertheless, an on-line version of Ohba 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 its chromatic number. This paper confirms the on-line version of Ohba conjecture for graphs G with independence number at most 3. We also study list colouring of complete multipartite graphs K3⋆ k with all parts of size 3. We prove that the on-line choice number of K3 ⋆ k is at most 3/2k, and present an alternate proof of Kierstead's result that its choice number is \lceil (4k-1)/3 \rceil. For general graphs G, we prove that if |V(G)| ≤ χ(G)+√(χ(G)) then its on-line choice number equals chromatic number.