Article ID Journal Published Year Pages File Type
419936 Discrete Applied Mathematics 2013 13 Pages PDF
Abstract

A strong edge-colouring of a graph GG is a proper edge-colouring such that every path of length 3 uses three different colours. In this paper we improve some previous results on the strong edge-colouring of subcubic graphs by showing that every subcubic graph with maximum average degree strictly less than 73 (resp. 52, 83, 207) can be strongly edge-coloured with six (resp. seven, eight, nine) colours. These upper bounds are optimal except the one of 83. Also, we prove that every subcubic planar graph without 44-cycles and 55-cycles can be strongly edge-coloured with nine colours.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,