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</em>
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 K2*(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 K2*k is on-line chromatic-choosable. We then present a minimal function g for which the graph K2*(k-1), 3 is on-line g-choosable. This is joint work with Young Soo Kwon, Daphne Der-Fen Liu, and Xuding Zhu.
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 K2*(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 K2*k is on-line chromatic-choosable. We then present a minimal function g for which the graph K2*(k-1), 3 is on-line g-choosable. This is joint work with Young Soo Kwon, Daphne Der-Fen Liu, and Xuding Zhu.