Nowhere-zero 4-flows and cycle double covers
type: Item
instance of: scholarly article
title: Nowhere-zero 4-flows and cycle double covers
zbMATH Open document ID: 0853.05064
DOI: 10.1016/0012-365X(95)00047-Z
author: Cun-Quan Zhang
published in: Discrete Mathematics
publication date: 1996-08-22T00:00:00Z
review text: In the present paper, a cycle is a graph containing only vertices of even degree. The longstanding cycle double cover conjecture states that each bridgeless graph \(G\) has a \(k\)-cycle double cover \((C_1, \dots, C_k)\) for some integer \(k\), i.e. each \(C_i\) is a cycle in \(G\) and each edge of \(G\) is contained in \(C_i\) for exactly two indices \(i \leq k\). A stronger version states that there even exists a 5-cycle double cover in each bridgeless graph. It is easy to prove that this version is true for all cubic edge-3-colourable graphs. Some time ago, M. Kochol and the reviewer constructed 5-cycle double covers in all cubic bridgeless graphs which are ``almost'' edge-3-colourable, i.e. which can be made edge-3-colourable by subdividing two edges by a vertex and by connecting the two new vertices by an edge [``Five cycle double covers of some cubic graphs'', J. Comb. Theory, Ser. B 64, No. 1, 119-125 (1995; Zbl 0820.05045)]. In the present paper, for \(k \in \{5,6,7\}\), the author presents a necessary and sufficient condition for a graph (not necessarily cubic) to have a \(k\)-cycle double cover which is based on the construction of M. Kochol and the reviewer. Moreover, he provides necessary and sufficient conditions for a graph to have a nowhere-zero 4-flow and he indicates how to extend the result of M. Kochol and the reviewer to arbitrary bridgeless graphs which ``almost'' admit a nowhere-zero 4-flow (for cubic graphs, the existence of a nowhere-zero 4-flow is equivalent to the existence of an edge-3-colouring). A similar extension has also been considered in ``Five cycle double covers of some cubic graphs''. Finally, the author proposes an approach for obtaining 5-cycle double covers in arbitrary bridgeless graphs without any restrictions. This approach is an obvious generalization of an approach for cubic graphs considered by the reviewer in a former version of ``Five cycle double covers of some cubic graphs'', see [``On cycle-double-covers of bridgel…
reviewed by: Andreas Huck
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 906905
zbMATH Keywords: cycle
zbMATH Keywords: cycle double cover conjecture
zbMATH Keywords: bridgeless graph
MaRDI profile type: Publication
cites work: Graphs with the Circuit Cover Property
cites work: Cycle covers of cubic multigraphs
cites work: Face colorings of embedded graphs
cites work: Q5422499
cites work: On circuit decomposition of planar Eulerian graphs
cites work: Cycle double covers of graphs with Hamilton paths
cites work: Five cycle double covers of some cubic graphs
cites work: Q3142415
cites work: Flows and generalized coloring theorems in graphs
cites work: Q3710541
cites work: Q3807237
cites work: Nowhere-zero 3-flows of highly connected graphs
cites work: Q3916595
cites work: Q5752592
cites work: Polyhedral decompositions of cubic graphs
cites work: Semi-duality and the cycle double cover conjecture
cites work: A Contribution to the Theory of Chromatic Polynomials
cites work: On the algebraic theory of graph colorings
cites work: Integer flows
cites work: Minimum cycle coverings and integer flows
cites work: Q3139762
cites work: Q4273859
description: scientific article; zbMATH DE number 906905