On-Line List Colouring of Complete Multipartite Graphs

Abstract

The Ohba Conjecture says that every graph $G$ with $|V(G)| \le 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 \ge 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)| \le 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.