Geodesic
Acyclic 3-choosability of plane graphs without cycles of length from~4 to~12
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 26-33

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., 2009). A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of $k$-cycles, where $4\le k\le S$. Here, we prove that every planar graph with no cycles with length from 4 to 12 is acyclically 3-choosable. Bibl. 18.
Keywords: planar graph, acyclic coloring, acyclic choosability. 
@article{DA_2009_16_5_a2,
     author = {O. V. Borodin},
     title = {Acyclic 3-choosability of plane graphs without cycles of length from~4 to~12},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {26--33},
     publisher = {mathdoc},
     volume = {16},
     number = {5},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_5_a2/}
}
TY  - JOUR
AU  - O. V. Borodin
TI  - Acyclic 3-choosability of plane graphs without cycles of length from~4 to~12
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 26
EP  - 33
VL  - 16
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_5_a2/
LA  - ru
ID  - DA_2009_16_5_a2
ER  - 
%0 Journal Article
%A O. V. Borodin
%T Acyclic 3-choosability of plane graphs without cycles of length from~4 to~12
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 26-33
%V 16
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_5_a2/
%G ru
%F DA_2009_16_5_a2
O. V. Borodin. Acyclic 3-choosability of plane graphs without cycles of length from~4 to~12. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 5, pp. 26-33. http://geodesic.mathdoc.fr/item/DA_2009_16_5_a2/