On-line choice number of complete multipartite graphs: an algorithmic approach (Q490305)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On-line choice number of complete multipartite graphs: an algorithmic approach |
scientific article |
Statements
On-line choice number of complete multipartite graphs: an algorithmic approach (English)
0 references
22 January 2015
0 references
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\).
0 references
online list coloring
0 references
Ohba's conjecture
0 references
paintability
0 references