Fulkerson's conjecture and circuit covers
Fulkerson's famous conjecture states that every bridgeless cubic graph has six perfect matchings such that each edge is in exactly two of the matchings. An algebraic cycle is a (possibly empty) graph where all vertices have even degree. In other words, it is the edge-disjoint union of ordinary cycles. A 3-cycle cover of a graph \(G\) consists of three subgraphs \(G_ 1\), \(G_ 2\), \(G_ 3\) of \(G\) that are algebraic cycles, and where every edge of \(G\) lies in some \(G_ i\). Since algebraic cycles can not contain bridges, every such \(G\) must be bridgeless. Conversely, \textit{F. Jaeger} showed that every bridgeless graph has some 3-cycle cover [J. Comb. Theory, Ser. B 26, 205-216 (1979; Zbl 0422.05028)]. In the present paper it is proven that, provided Fulkerson's conjecture were true, every bridgeless graph \(G = (V,E)\) had some 3-cycle cover \(G_ 1\), \(G_ 2\), \(G_ 3\) such that \(| E(G_ 1)| + | E(G_ 2)| + | E(G_ 3)| \leq {22 \over 15} | E(G)|\). This would improve the bound \({5 \over 3} | E(G) |\) of \textit{J. C. Bermond}, \textit{B. Jackson}, and \textit{F. Jaeger} [J. Comb. Theory, Ser. B 35, 297-308 (1983; Zbl 0559.05037)], which however is not dependent on Fulkerson's conjecture. Furthermore the authors present examples that the bound \({22 \over 15} | E(G)|\) is sharp.
scientific article; zbMATH DE number 599870