کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429124 | 687052 | 2009 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two adjacent vertices in G receive the same color and (ii) no bicolored cycles exist in G. A list assignment of G is a function L that assigns to each vertex v∈V(G) a list L(v) of available colors. Let G be a graph and L be a list assignment of G. The graph G is acyclically L-list colorable if there exists an acyclic coloring ϕ of G such that ϕ(v)∈L(v) for all v∈V(G). If G is acyclically L-list colorable for any list assignment L with |L(v)|⩾k for all v∈V(G), then G is acyclically k-choosable. In this paper, we prove that every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 109, Issues 21–22, 31 October 2009, Pages 1193-1196
Journal: Information Processing Letters - Volume 109, Issues 21–22, 31 October 2009, Pages 1193-1196