Equitable list coloring of graphs
Let \(G\) be a graph. Then \(G\) is equitably \(k\)-choosable if for each list assignment \(L\) so that \(\left| L(v)\right| =k\) for every vertex \(v\) of \(G\) there is a proper coloring \(\pi \) so that \(\pi (v)\in L(v),\) for all \( v\) in \(G,\) and each color appears on at most \(\left\lceil \frac{\left| G\right| }{k}\right\rceil \) vertices. \textit{A. V. Kostochka} et al. [J. Graph Theory 44, 166-177 (2003; Zbl 1031.05050)] conjectured that if \(k\geq \Delta (G)+1,\) then \(G\) is equitably \(k\)-choosable. The authors of the present paper show that the conjecture is true for all graphs of maximum degree \(3,\) and also in the case when \(k\geq (\Delta -1)^{2}.\)
scientific article; zbMATH DE number 2158131