On parsimonious edge-colouring of graphs with maximum degree three
Jean‐Luc Fouquet, Jean-Marie Vanherpe · arXiv (Cornell University) · 2008
In a graph $G$ of maximum degree $Δ$ let $γ$ denote the largest fraction of edges that can be $Δ$ edge-coloured. Albertson and Haas showed that $γ\geq 13/15$ when $G$ is cubic . We show here that this result can be extended to graphs with maximum degree 3 with the exception of a graph on 5 vertices. Moreover, there are exactly two graphs with maximum degree 3 (one being obviously the Petersen graph) for which $γ= 13/15$. This extends a result given by Steffen. These results are obtained by using structural properties of the so called $δ$-minimum edge colourings for graphs with maximum degree 3. Keywords : Cubic graph; Edge-colouring