×

zbMATH — the first resource for mathematics

List improper colorings of planar graphs with prescribed girth. (English) Zbl 0940.05027
A graph \(G\) is said to be \((m,d)^{*}\)-choosable, if for every list assignment \(L\), where \(|L(v)|\geq m\) for every \(v\in V(G)\), there exists an \(L\)-coloring of \(G\) such that every vertex of \(G\) has at most \(d\) neighbors colored with the same color as itself. Denote by \(g_{d}\) the smallest number such that every planar graph of girth at least \(g_{d}\) is \((2,d)^{*}\)-choosable. In this paper it is shown that \(6\leq g_{1}\leq 9\); \(2\leq g_{2}\leq 7\); \(5\leq g_{3}\leq 6\) and \(g_{d}=5\) for every \(d\geq 4\).

MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI