کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648996 1632436 2010 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On acyclic 4-choosability of planar graphs without short cycles
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On acyclic 4-choosability of planar graphs without short cycles
چکیده انگلیسی

Let G=(V,E)G=(V,E) be a graph. A proper vertex coloring of GG is acyclic if GG contains no bicolored cycle. Namely, every cycle of GG must be colored with at least three colors. GG is acyclicallyLL-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 planar graphs with neither {4,5}{4,5}-cycles nor 8-cycles having a triangular chord are acyclically 4-choosable. This implies that planar graphs either without {4,5,7}{4,5,7}-cycles or without {4,5,8}{4,5,8}-cycles are acyclically 4-choosable.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issues 15–16, 28 August 2010, Pages 2113–2118
نویسندگان
, ,