کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423953 1632593 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bounds and complexity results for strong edge colouring of subcubic graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Bounds and complexity results for strong edge colouring of subcubic graphs
چکیده انگلیسی

A strong edge colouring of a graph G is a proper edge colouring such that every path of length 3 uses three colours. In this paper, we give some upper bounds for the minimum number of colours in a strong edge colouring of subcubic graphs as a function of the maximum average degree. We also prove the NP-completeness of the strong edge k-colouring problem for some restricted classes of subcubic planar graphs when k=4,5,6.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 463-468
نویسندگان
, , ,