Volume 16, No 5, 2009, P. 2633
UDC 519.172.2
O. V. Borodin
Acyclic 3choosability of plane graphs without cycles of length from 4 to 12
Abstract:
Every planar graph is known to be acyclically 7choosable and is conjectured to be acyclically 5choosable (Borodin et al., 2002). This conjecture, if proved, would imply both Borodin's acyclic 5color theorem (1979) and Thomassen's 5choosability 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 3choosable. In particular, a planar graph of girth at least 7 is acyclically 3colorable (Borodin, Kostochka, and Woodall, 1999) and acyclically 3choosable (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 3choosable.
Bibl. 18.
Keywords: planar graph, acyclic coloring, acyclic choosability.
Borodin Oleg Veniaminovich ^{1}
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
email: brdnoleg@math.nsc.ru
