|
Diskretnyi Analiz i Issledovanie Operatsii, 2009, Volume 16, Issue 5, Pages 26–33
(Mi da584)
|
|
|
|
This article is cited in 15 scientific papers (total in 15 papers)
Acyclic 3-choosability of plane graphs without cycles of length from 4 to 12
O. V. Borodin S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
Abstract:
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.
Received: 13.05.2009 Revised: 17.06.2009
Citation:
O. V. Borodin, “Acyclic 3-choosability of plane graphs without cycles of length from 4 to 12”, Diskretn. Anal. Issled. Oper., 16:5 (2009), 26–33; J. Appl. Industr. Math., 4:2 (2010), 158–162
Linking options:
https://www.mathnet.ru/eng/da584 https://www.mathnet.ru/eng/da/v16/i5/p26
|
|