Article ID Journal Published Year Pages File Type
4648185 Discrete Mathematics 2012 7 Pages PDF
Abstract
There exist planar acyclically non-4-colorable bipartite graphs (Kostochka and Mel'nikov, 1976 [25]). This partly explains the fact that in all previously known sufficient conditions for the acyclic 4-choosability of planar graphs the 4-cycles are completely forbidden. In this paper we allow 4-cycles nonadjacent to relatively short cycles; namely, it is proved that a planar graph is acyclically 4-choosable if it does not contain an i-cycle adjacent to a j-cycle, where 3≤j≤6 if i=3 and 4≤j≤7 if i=4. In particular, this absorbs all the above-mentioned results.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,