Equitable list coloring of graphs
type: Item
instance of: scholarly article
title: Equitable list coloring of graphs
zbMATH Open document ID: 1063.05051
author: Ko-Wei Lih
author: Weifan Wang
published in: Taiwanese Journal of Mathematics
publication date: 2005-04-18T00:00:00Z
review text: 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}.\)
reviewed by: Peter Horák
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 2158131
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.11650/twjm/1500407716
OpenAlex ID: W4230620595
DOI: 10.11650/TWJM/1500407716
Recommended article: Equitable and equitable list colorings of graphs
Recommended article: Equitable list coloring of graphs with bounded degree
Recommended article: A list analogue of equitable coloring
Recommended article: Q5650698
Recommended article: Q4247466
Recommended article: Equitable list-coloring for graphs of maximum degree 3
Recommended article: Q4391847
Recommended article: On equitable and equitable list colorings of series-parallel graphs
Recommended article: Equitable list coloring and treewidth
Recommended article: Equitable list colorings of planar graphs without short cycles
description: scientific article; zbMATH DE number 2158131