On even cycle decompositions of 4-regular line graphs

We prove that the Petersen colouring conjecture implies a conjecture of Markström saying that the line graph of every bridgeless cubic graph is decomposable into cycles of even length. In addition, we describe two infinite families of 4-regular graphs: the first family consists of 3-connected graphs...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2013-09, Vol.313 (17), p.1697-1699
Main Authors: Máčajová, Edita, Mazák, Ján
Format: Article
Language:English
Subjects:
Colouring
Cubic graph
Decomposition
Even cycle decomposition
Graphs
Line graph
Mathematical analysis
Petersen colouring conjecture
Signed graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove that the Petersen colouring conjecture implies a conjecture of Markström saying that the line graph of every bridgeless cubic graph is decomposable into cycles of even length. In addition, we describe two infinite families of 4-regular graphs: the first family consists of 3-connected graphs with no even cycle decomposition and the second one consists of 4-connected signed graphs with no even cycle decomposition.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2013.04.027