Improper Choosability of Planar Graphs without 4-Cycles
Yingqian Wang, Lingji Xu · SIAM Journal on Discrete Mathematics · 2013
Let $k\ge 2$ be a positive integer, and let $d$ be a nonnegative integer. A graph $G$ is $d$-improperly $k$-choosable, or simply, $(k,d)$-choosable if, for every list assignment $L$ with $|L(v)|\geq k$ for every $v\in V (G)$, there exists an $L$-coloring of $G$ such that each vertex of $G$ has at most $d$ neighbors colored the same color as itself. It is known that every planar graph with cycles of length neither 4 nor $k$ for some $k\in\{5,6,7,8,9\}$ is $(3,1)$-choosable. In this paper, we prove that every planar graph without cycles of length 4 is $(3,1)$-choosable. This is best possible in the following two senses: (i) there are planar graphs which are not $(3,1)$-colorable, hence not $(3,1)$-choosable; (ii) there are planar graphs without 4-cycles which are not $(3,0)$-colorable, hence not $(3,0)$-choosable.