کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650340 | 1342485 | 2008 | 10 صفحه PDF | دانلود رایگان |
A proper vertex coloring of a graph G=(V,E)G=(V,E) is acyclic if GG contains no bicolored cycle. A graph GG is acyclically LL-list colorable if for a given list assignment L={L(v):v∈V}L={L(v):v∈V}, there exists a proper acyclic coloring ππ of GG such that π(v)∈L(v)π(v)∈L(v) for all v∈Vv∈V. If GG is acyclically LL-list colorable for any list assignment with |L(v)|≥k|L(v)|≥k for all v∈Vv∈V, then GG is acyclically kk-choosable. In this paper we prove that every planar graph without 4-cycles and without two 3-cycles at distance less than 3 is acyclically 5-choosable. This improves a result in [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (2006) 281–300], which says that planar graphs of girth at least 5 are acyclically 5-choosable.
Journal: Discrete Mathematics - Volume 308, Issue 24, 28 December 2008, Pages 6216–6225