RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2011 Volume 52, Number 3, Pages 522–541 (Mi smj2217)

This article is cited 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.

UDC: 519.17

Received: 18.07.2010


 English version:
Siberian Mathematical Journal, 2011, 52:3, 411–425

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025