Article ID Journal Published Year Pages File Type
6423953 Electronic Notes in Discrete Mathematics 2011 6 Pages PDF
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
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Bounds and complexity results for strong edge colouring of subcubic graphs
Authors
, , ,