Hajós' conjecture and small cycle double covers of planar graphs
type: Item
instance of: scholarly article
title: Hajós' conjecture and small cycle double covers of planar graphs
zbMATH Open document ID: 0766.05067
DOI: 10.1016/0012-365X(92)90610-R
author: K. Seyffarth
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: A graph is said to be even if all its vertices have even degree, and it is well known that the edge set of a graph \(G\) can be partitioned into cycles if and only if \(G\) is even. Such a partition of the edges of a graph is called a cycle decomposition of the graph. We let \(c(G)\) denote the minimum number of cycles required in a cycle decomposition of an even graph \(G\). A cycle double cover, \({\mathcal C}\), of a graph \(G\) is a collection of cycles containing every edge of \(G\) exactly twice. If \(G\) has \(n\) vertices, then \({\mathcal C}\) is called a small cycle double cover if it contains at most \(n-1\) cycles. There exist even graphs \(G\) on \(n\) vertices for which \(c(G)\geq\lfloor(n-1)/2\rfloor\), and \textit{G. Hajós} conjectured that every simple even graph \(G\) on \(n\) vertices has \(c(G)\leq\lfloor(n-1)/2\rfloor\). We prove this conjecture for planar graphs (a somewhat incomplete proof was given earlier by \textit{J. Tao}). We then discuss the connection between this result and small cycle double covers of graphs.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 89910
zbMATH Keywords: Hajós' conjecture
zbMATH Keywords: cycle decomposition
zbMATH Keywords: cycle double cover
zbMATH Keywords: planar graphs
Wikidata QID: Q122927381
MaRDI profile type: Publication
cites work: Q3360905
cites work: Q5422499
cites work: Q5284008
cites work: What is the smallest number of dicycles in a dicycle decomposition of an eulerian digraph?
cites work: Q3718751
cites work: Q3795702
cites work: Flows and generalized coloring theorems in graphs
cites work: Q5539649
cites work: On Eulerian and regular perfect path double covers of graphs
cites work: Small cycle double covers of 4-connected planar graphs
cites work: Q3916595
cites work: Polyhedral decompositions of cubic graphs
description: scientific article; zbMATH DE number 89910