Nowhere-zero 4-flows and cycle double covers
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)].
scientific article; zbMATH DE number 906905
scientific article