کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418699 | 681709 | 2014 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Strong edge-colouring of sparse planar graphs
ترجمه فارسی عنوان
رنگ آمیزی لبه های قوی گرافهای مسطح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودارهای پلانار، غرق شدن لبه رنگ مناسب، قوی لبه رنگ آمیزی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A strong edge-colouring of a graph is a proper edge-colouring where each colour class induces a matching. It is known that every planar graph with maximum degree ΔΔ has a strong edge-colouring with at most 4Δ+44Δ+4 colours. We show that 3Δ+13Δ+1 colours suffice if the graph has girth 6, and 4Δ4Δ colours suffice if Δ≥7Δ≥7 or the girth is at least 5. In the last part of the paper, we raise some questions related to a long-standing conjecture of Vizing on proper edge-colouring of planar graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 179, 31 December 2014, Pages 229–234
Journal: Discrete Applied Mathematics - Volume 179, 31 December 2014, Pages 229–234
نویسندگان
Julien Bensmail, Ararat Harutyunyan, Hervé Hocquard, Petru Valicov,