On-line list colouring of complete multipartite graphs

Seog-Jin Kim ; Young Soo Kwon ; Daphne Der-Fen Liu ; Xuding Zhu

The electronic journal of combinatorics, Tome 19 (2012) no. 1

Résumé

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.

Détail

DOI : 10.37236/2050

Classification : 05C15
Mots-clés : on-line chromatic-choosable graph