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

چکیده انگلیسی
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
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 463-468
نویسندگان
Hervé Hocquard, Pascal Ochem, Petru Valicov,