Acyclic 5-choosability of planar graphs without 4-cycles |
| |
Authors: | O. V. Borodin A. O. Ivanova |
| |
Affiliation: | 1.Sobolev Institute of Mathematics and Novosibirsk State University,Novosibirsk,Russia |
| |
Abstract: | ![]() The conjecture on the acyclic 5-choosability of planar graphs (Borodin et al., 2002) as yet has been verified only for several restricted classes of graphs: those of girth at least 5 (Montassier, Ochem, and Raspaud, 2006), without 4- and 5-cycles or without 4- and 6-cycles (Montassier, Raspaud, and Wang, 2007), with neither 4-cycles nor chordal 6-cycles (Zhang and Xu, 2009), with neither 4- cycles nor two 3-cycles at distance less than 3 (Chen and Wang, 2008), and with neither 4-cycles nor intersecting 3-cycles (Chen and Raspaud, 2010). Wang and Chen (2009) proved that the planar graphs without 4-cycles are acyclically 6-choosable. We prove that a planar graph without 4-cycles is acyclically 5-choosable, which is a common strengthening of all above-mentioned results. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|