Cycle double cover conjecture

Cycle Double Cover Conjecture

For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two.

Stronger conjectures than the Cycle Double Cover Conjecture

The circular embedding conjecture

"Every 2-connected graph may be embedded in a surface so that the boundary of each face is a cycle."

This conjecture implies the cycle double cover conjecture. Both conjectures are equivalent for cubic graphs. The circular embedding conjecture can be made into a stronger conjecture by adding the condition that an embedding exists for which the dual graph is 5-colorable. This stronger version implies the five cycle double cover conjection.

The five cycle double cover conjecture

"Every bridgeless graph has a (5,2)-cycle-cover."

This is a strengthening of the cycle double cover conjecture because every binary cycle can be written as a disjoint union of edge sets of ordinary cycles.

The faithful cover conjecture

"If G=(V,E) is a graph, p: E -> Z is admissable and p(e) is even for every e in E, then (G,p) has a faithful cover."

The cycle double cover conjecture is a special case of this conjecture. We can reformulate the cycle double cover conjecture: (G,2) has a faithful cover for every graph G with no bridge, where 2 is the constant function with value 2.

Decomposing Eulerian graphs

"If G is a 6-edge-connected Eulerian graph and P is a 2-transition system for G, then (G,P) has a compatible decomposition."

From the link above we obtain a proof that this concjecture implies the cycle double cover conjecture: "Let G be a graph and let G' be the graph obtained from G by replacing each edge e of G by two edges e', e'' in parallel. Let P be the 2-transition system of G with {e',e''} in P(v) whenever e' and e'' are incident with v. Now, G' is an Eulerian graph and every compatible decomposition of (G',P) gives a cycle double cover of G. Since the cycle double cover conjecture can be reduced to graphs which are 3-edge-connected, the above conjecture would imply the cycle double cover conjecture."

Berge-Fulkerson conjecture

"If G is a bridgeless cubic graph, then there exist 6 perfect matchings M1,...,M6 of G with the property that every edge of G is contained in exactly two of M1,...,M6."

Most of the conjectures named at this website are related to the Berge-Fulkerson conjecture. For example, this conjecture can be stated in a similar way as the five cycle double cover conjecture: every graph with no cut-edge has a (6,4)-cycle-cover.