(3, 1)*-choosability of planar graphs without adjacent short cycles

A list assignment of a graph G is a function L that assigns a list L(v) of colors to each vertex v∈V(G). An (L,d)⁎-coloring is a mapping π that assigns a color π(v)∈L(v) to each vertex v∈V(G) so that at most d neighbors of v receive color π(v). A graph G is said to be (k,d)⁎-choosable if it admits an (L,d)⁎-coloring for every list assignment L with |L(v)|⩾k for all v∈V(G). In 2001, Lih et al. [Lih, K., Z. Song, W. Wang, and K. Zhang, A note on list improper coloring planar graphs, Appl. Math. Lett. 14 (2001), 269–273] proved that planar graphs without 4- and l-cycles are (3,1)⁎-choosable, where l∈{5,6,7}. Later, Dong and Xu [Dong, W., and B. Xu, A note on list improper coloring of plane graphs, Discrete Appl. Math. 157 (2009), 433–436] proved that planar graphs without 4- and l-cycles are (3,1)⁎-choosable, where l∈{8,9}.There exist planar graphs containing 4-cycles that are not (3,1)⁎-choosable (Crown, Crown and Woodall, 1986 [Cowen, L., R. Cowen, and D. Woodall, Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory 10 (1986), 187–195]). This partly explains the fact that in all above known sufficient conditions for the (3,1)⁎-choosability of planar graphs the 4-cycles are completely forbidden. In this paper we allow 4-cycles nonadjacent to relatively short cycles. More precisely, we prove that every planar graph without 4-cycles adjacent to 3- and 4-cycles is (3,1)⁎-choosable. This is a common strengthening of all above mentioned results. Moreover as a consequence we give a partial answer to a question of Xu and Zhang [Xu, B., and H. Zhang, Every toroidal graph without adjacent triangles is (4,1)⁎-choosable, Discrete Appl. Math. 155 (2007), 74–78] and show that every planar graph without 4-cycles is (3,1)⁎-choosable.