کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
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
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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
Journal: Discrete Mathematics - Volume 317, 28 February 2014, Pages 19–32
نویسندگان
Marthe Bonamy, Benjamin Lévêque, Alexandre Pinlou,