کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428369 | 686643 | 2006 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A note on the not 3-choosability of some families of planar graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A graph G is L-list colorable if for a given list assignment , there exists a proper coloring c of G such that c(v)∈L(v) for all v∈V. If G is L-list colorable for any list assignment with |L(v)|⩾k for all v∈V, then G is said k-choosable. In [M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995) 325–328] and [M. Voigt, A non-3-choosable planar graph without cycles of length 4 and 5, 2003, Manuscript], Voigt gave a planar graph without 3-cycles and a planar graph without 4-cycles and 5-cycles which are not 3-choosable. In this note, we give smaller and easier graphs than those proposed by Voigt and suggest an extension of Erdös' relaxation of Steinberg's conjecture to 3-choosability.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 99, Issue 2, 31 July 2006, Pages 68-71
Journal: Information Processing Letters - Volume 99, Issue 2, 31 July 2006, Pages 68-71