Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419936 | Discrete Applied Mathematics | 2013 | 13 Pages |
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
Hervé Hocquard, Mickaël Montassier, André Raspaud, Petru Valicov,