On-line list colouring of complete multipartite graphs (Q426807)

Summary: The Ohba Conjecture says that every graph \(G\) with \(|V(G)| \leq 2 \chi(G)+1\) is chromatic choosable. This paper studies an on-line version of Ohba Conjecture. We prove that unlike the off-line case, for \(k \geq 3\), the complete multipartite graph \(K_{2\star (k-1), 3}\) is not on-line chromatic-choosable. Based on this result, the on-line version of Ohba Conjecture is modified as follows: Every graph \(G\) with \(|V(G)| \leq 2 \chi(G)\) is on-line chromatic choosable. We present an explicit strategy to show that for any positive integer \(k\), the graph \(K_{2\star k}\) is on-line chromatic-choosable. We then present a minimal function \(g\) for which the graph \(K_{2 \star (k-1), 3}\) is on-line \(g\)-choosable.