Title of article
Bounds and complexity results for strong edge colouring of subcubic graphs
Author/Authors
Hervé Hocquard، نويسنده , , Hervé and Ochem، نويسنده , , Pascal and Valicov، نويسنده , , Petru، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2011
Pages
6
From page
463
To page
468
Abstract
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 .
Keywords
strong edge colouring , subcubic graphs , maximum average degree , NP-Completeness
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2011
Journal title
Electronic Notes in Discrete Mathematics
Record number
1455869
Link To Document