On-line choice number of complete multipartite graphs: an algorithmic approach (Q490305)

Summary: 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\left(\frac{p^2}{2}-\frac{3p}{2}+1\right)k_p\geqslant 0\), where \(k_p\) denotes the number of parts of cardinality \(p\), then \(G\) is on-line chromatic-choosable. (2) If \(|V(G)|\leq\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 \(\left(m+\frac{1}{2}-\sqrt{2m-2}\right)k\) for \(m\geq 3\).