کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419740 683856 2009 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
List-coloring graphs without K4,kK4,k-minors
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
List-coloring graphs without K4,kK4,k-minors
چکیده انگلیسی

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
نویسندگان
,