On-line list colouring of complete multipartite graphs

Seog-Jin Kim (김석진)

Dept. of Mathematics Education, Konkuk University, Seoul, Korea.

Dept. of Mathematics Education, Konkuk University, Seoul, Korea.

2011/4/18 Wed 4PM-5PM

The well-known Ohba Conjecture says that every graph G with |V(G)|≤ 2χ(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≥3, the complete multipartite graph K

This paper studies an on-line version of Ohba Conjecture. We prove that unlike the off-line case, for k≥3, the complete multipartite graph K

_{2*(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)|≥ 2χ(G) is on-line chromatic choosable. We present an explicit strategy to show that for any positive integer k, the graph K_{2*k}is on-line chromatic-choosable. We then present a minimal function g for which the graph K_{2*(k-1), 3}is on-line g-choosable. This is joint work with Young Soo Kwon, Daphne Der-Fen Liu, and Xuding Zhu.Tags: 김석진