کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653498 1632778 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
List coloring the square of sparse graphs with large degree
ترجمه فارسی عنوان
لیست رنگ مربع گرافیت های ضعیف با درجه بزرگ
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We strengthen their result and prove that there exists a function f such that the square of any graph with maximum average degree m<3 and maximum degree Δ≥f(m) is list (Δ+1)-colorable. Note the planarity assumption is dropped. This bound of 3 is optimal in the sense that the above-mentioned planar graphs with girth 6 have maximum average degree less than 3 and arbitrarily large maximum degree, while their square cannot be (Δ+1)-colored. The same holds for list injective Δ-coloring.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 41, October 2014, Pages 128-137
نویسندگان
, , ,