Nowhere-zero 4-flows and cycle double covers

DOI10.1016/0012-365X(95)00047-ZMaRDI QIDQ1918555zbMATH OpenFDO

Publication date 22 August 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00047-Z

bridgeless graph cycle cycle double cover conjecture

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 bridgeless graphs with Hamiltonian paths, preprint series of the Institute of Mathematics, University of Hannover, 254 (1993)].

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Nowhere-zero 4-flows and cycle double covers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1918555)