کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647534 1632425 2014 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Graphs with maximum degree Δ≥17Δ≥17 and maximum average degree less than 33 are list 22-distance (Δ+2)(Δ+2)-colorable
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Graphs with maximum degree Δ≥17Δ≥17 and maximum average degree less than 33 are list 22-distance (Δ+2)(Δ+2)-colorable
چکیده انگلیسی

For graphs of bounded maximum average degree, we consider the problem of 2-distance coloring  . This is the problem of coloring the vertices while ensuring that two vertices that are adjacent or have a common neighbor receive different colors. It is already known that planar graphs of girth at least 66 and of maximum degree ΔΔ are list 2-distance (Δ+2)(Δ+2)-colorable when Δ≥24Δ≥24 (Borodin and Ivanova (2009)) and 2-distance (Δ+2)(Δ+2)-colorable when Δ≥18Δ≥18 (Borodin and Ivanova (2009)). We prove here that Δ≥17Δ≥17 suffices in both cases. More generally, we show that graphs with maximum average degree less than 33 and Δ≥17Δ≥17 are list 2-distance (Δ+2)(Δ+2)-colorable. The proof can be transposed to list injective (Δ+1)(Δ+1)-coloring.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 317, 28 February 2014, Pages 19–32
نویسندگان
, , ,