首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号