کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418699 681709 2014 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Strong edge-colouring of sparse planar graphs
ترجمه فارسی عنوان
رنگ آمیزی لبه های قوی گرافهای مسطح
کلمات کلیدی
نمودارهای پلانار، غرق شدن لبه رنگ مناسب، قوی لبه رنگ آمیزی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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