On Parsimonious Edge-Colouring of Graphs with Maximum Degree Three |
| |
Authors: | J.-L. Fouquet J.-M. Vanherpe |
| |
Affiliation: | 1. L.I.F.O., Faculté des Sciences, Université d’Orléans, B.P. 6759, 45067, Orléans Cedex 2, France
|
| |
Abstract: | In a graph G of maximum degree Δ, let γ denote the largest fraction of edges that can be Δ edge-coloured. Albertson and Haas showed that ${gamma geq frac{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 ${gamma = frac{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: | |
本文献已被 SpringerLink 等数据库收录! |
|