On (3,1)? ( 3 , 1 ) ? -choosability of planar graphs without adjacent short cycles
A list assignment of a graph G G is a function L L that assigns a list L(v) L ( v ) of colors to each vertex v?V(G) v ? V ( G ) . An (L,d)? ( L , d ) ? -coloring is a mapping ? ? that assigns a color ?(v)?L(v) ? ( v ) ? L ( v ) to each vertex v?V(G) v ? V ( G ) so that at most d d neighbors of v v receive the color ?(v) ? ( v ) . A graph G G is said to be (k,d)? ( k , d ) ? -choosable if it admits an (L,d)? ( L , d ) ? -coloring for every list assignment L L with |L(v)|?k | L ( v ) | ? k for all v?V(G) v ? V ( G ) . In 2001, Lih et al. (2001) [6] proved that planar graphs without 4- and l l -cycles are (3,1)? ( 3 , 1 ) ? -choosable, where l?{5,6,7} l ? { 5 , 6 , 7 } . Later, Dong and Xu (2009) [3] proved that planar graphs without 4- and l l -cycles are (3,1)? ( 3 , 1 ) ? -choosable, where l?{8,9} l ? { 8 , 9 } . There exist planar graphs containing 4-cycles that are not (3,1)? ( 3 , 1 ) ? -choosable (Cowen et al., 1986 [1]). This partly explains the fact that in all above known sufficient conditions for the (3,1)? ( 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)? ( 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 ofXu and Zhang (2007) [11] and show that every planar graph without 4-cycles is (3,1)? ( 3 , 1 ) ? -choosable.
planar graphs cycle improper choosability