Geodesic
Acyclic $3$-choosability of planar graphs with no cycles of length from~$4$ to~$11$
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 275-283

Voir la notice de l'article provenant de la source Math-Net.Ru

Every planar graph is known to be acyclically $7$-choosable and is conjectured to be acyclically $5$-choosable (Borodin et al., 2002). This conjecture if proved would imply both Borodin's acyclic $5$-color theorem (1979) and Thomassen's $5$-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically $4$- and $3$-choosable. In particular, a planar graph of girth at least $7$ is acyclically $3$-colorable (Borodin, Kostochka and Woodall, 1999) and acyclically $3$-choosable (Borodin et al., 2010). A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of $k$-cycles, where $4\le k\le C$. Here, we prove that every planar graph with no cycles of length from $4$ to $11$ is acyclically $3$-choosable.
Keywords: acyclic coloring, planar graph, forbidden cycles. 
@article{SEMR_2010_7_a19,
     author = {O. V. Borodin and A. O. Ivanova},
     title = {Acyclic $3$-choosability of planar graphs with no cycles of length from~$4$ to~$11$},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {275--283},
     publisher = {mathdoc},
     volume = {7},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2010_7_a19/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
TI  - Acyclic $3$-choosability of planar graphs with no cycles of length from~$4$ to~$11$
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2010
SP  - 275
EP  - 283
VL  - 7
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2010_7_a19/
LA  - en
ID  - SEMR_2010_7_a19
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%T Acyclic $3$-choosability of planar graphs with no cycles of length from~$4$ to~$11$
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2010
%P 275-283
%V 7
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2010_7_a19/
%G en
%F SEMR_2010_7_a19
O. V. Borodin; A. O. Ivanova. Acyclic $3$-choosability of planar graphs with no cycles of length from~$4$ to~$11$. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 7 (2010), pp. 275-283. http://geodesic.mathdoc.fr/item/SEMR_2010_7_a19/