On parsimonious edge-colouring of graphs with maximum degree threeReport as inadecuate

On parsimonious edge-colouring of graphs with maximum degree three - Download this document for free, or read online. Document in PDF available to download.

1 LIFO - Laboratoire d-Informatique Fondamentale d-Orléans

Abstract : In a graph $G$ of maximum degree $\Delta$ let $\gamma$ denote the largest fraction of edges that can be $\Delta$ 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 $\delta$-minimum edge colourings for graphs with maximum degree $3$.\\ {\bf Keywords :} Cubic graph; Edge-colouring; oindent {\bf Mathematics Subject Classification 2010 :} 05C15.

Keywords : Cubic graphs edge partition

Author: Jean-Luc Fouquet - Jean-Marie Vanherpe -

Source: https://hal.archives-ouvertes.fr/


Related documents