کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649151 | 1632435 | 2010 | 9 صفحه PDF | دانلود رایگان |
Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al. 2002 [4]). 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 have also been obtained for a planar graph to be acyclically 4- and 3-choosable.We prove that each planar graph of girth at least 7 is acyclically 3-choosable. This is a common strengthening of the facts that such a graph is acyclically 3-colorable (Borodin et al., 1999 [10]) and that a planar graph of girth at least 8 is acyclically 3-choosable (Montassier et al., 2006 [19]). More generally, we prove that every graph with girth at least 7 and maximum average degree less than 145 is acyclically 3-choosable.
Journal: Discrete Mathematics - Volume 310, Issues 17–18, 28 September 2010, Pages 2426–2434