Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648185 | Discrete Mathematics | 2012 | 7 Pages |
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
Oleg V. Borodin, Anna O. Ivanova,