کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419740 | 683856 | 2009 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
List-coloring graphs without K4,kK4,k-minors
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
In this note, it is shown that every graph with no K4,kK4,k-minor is 4k4k-list-colorable. We also give an extremal function for the existence for a K4,kK4,k-minor. Our proof implies that there is a linear time algorithm for showing that either GG has a K4,kK4,k-minor or GG is 4k4k-choosable. In fact, if the latter holds, then the algorithm gives rise to a 4k4k-list-coloring.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 4, 28 February 2009, Pages 659–662
Journal: Discrete Applied Mathematics - Volume 157, Issue 4, 28 February 2009, Pages 659–662
نویسندگان
Ken-ichi Kawarabayashi,