On-Line Choice Number of Complete Multipartite Graphs: an Algorithmic Approach

Abstract

This paper studies the on-line choice number on complete multipartite graphs with independence number $m$. We give a unified strategy for every prescribed $m$. Our main result leads to several interesting consequences comparable to known results. (1) If $k_1-{\sum }_{p=2}^m(\frac{p^2}{2}-\frac{3p}{2}+1)k_p\ge 0$, where $k_p$ denotes the number of parts of cardinality $p$, then $G$ is on-line chromatic-choosable. (2) If $|V(G)|\le \frac{m^2-m+2}{m^2-3m+4}\chi (G)$, then $G$ is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs $K_{m\star k}$ is at most $(m+\frac{1}{2}-\sqrt{2m-2})k$ for $m\ge 3$.