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
Full Text: