|
Sibirskii Matematicheskii Zhurnal, 2011, Volume 52, Number 3, Pages 522–541
(Mi smj2217)
|
|
|
|
This article is cited in 15 scientific papers (total in 15 papers)
Acyclic 5-choosability of planar graphs without 4-cycles
O. V. Borodinab, A. O. Ivanovac a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University, Novosibirsk
c Institute for Mathematics and Informatics, Yakutsk State University, Yakutsk
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:
graph, planar graph, coloring, acyclic coloring, list coloring.
Received: 18.07.2010
Citation:
O. V. Borodin, A. O. Ivanova, “Acyclic 5-choosability of planar graphs without 4-cycles”, Sibirsk. Mat. Zh., 52:3 (2011), 522–541; Siberian Math. J., 52:3 (2011), 411–425
Linking options:
https://www.mathnet.ru/eng/smj2217 https://www.mathnet.ru/eng/smj/v52/i3/p522
|
Statistics & downloads: |
Abstract page: | 366 | Full-text PDF : | 76 | References: | 69 | First page: | 11 |
|