Acyclic 5‐choosability of planar graphs without adjacent short cycles |
| |
| Authors: | O. V. Borodin A. O. Ivanova |
| |
| Affiliation: | 1. Institute of Mathematics of Siberian Branch of the Russian Academy of Sciences and Novosibirsk State University Novosibirsk 630090, Russia;2. Institute of Mathematics at Yakutsk State University, Yakutsk 677891, Russia |
| |
| Abstract: | The conjecture on acyclic 5‐choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4‐cycles. We prove that a planar graph is acyclically 5‐choosable if it does not contain an i‐cycle adjacent to a j‐cycle where 3?j?5 if i = 3 and 4?j?6 if i = 4. This result absorbs most of the previous work in this direction. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:169‐176, 2011 |
| |
| Keywords: | planar graph acyclic coloring acyclic choosability |
|
