k-flow graph double cover conjecture

A graph G is called a k-flow graph if G admits a nowhere zero k-flow. Thus a 2-flow graph is a cycle (i.e., each
vertex has even degree).

k-flow graph double cover conjecture (unoriented version):
Suppose G is a bridgeless graph and 2 <= k <= 5 is an integer. Then G has (7-k)-subgraphs H_1, H_2, ..., H_{7-k} such that each H_i is a k-flow graph and each edge of G is contained in exactly two of the H_i's.

The special case k=2 of the above conjecture reads as follows:

5-cycle double cover conjecture (unoriented version):
Each bridgeless graph has a 5-cycle double cover, i.e. G has 5 cycles, their union covers each edge exactly twice.

 The 5-cycle double cover conjecture is due to Celmins [Ce84] and Preissmann [Pr81]. 

The special case k=5, both oriented and unoriented  5-flow graph double cover conjecture  are equivalent to the following 5-flow conjecture of  Tutte [Tu54].

5 flow-conjecture:
Every bridgeless graph G admits a nowhere zero 5-flow.

The special case k=4 of the k-flow graph double cover conjecture  was proposed by DeVos as well, and here is a backgroud discussion about the problem. 

A directed graph H admits a positive k-flow if the underline graph of H has a nowhere zero k-flow f such that f(a) >0 for each arc a of H.   An oriented double cover of a (undirected) graph G is a family of directed graphs, each being an orientation of a subgraph of G, whose union covers each edge of G exactly twice, once in each direction. Each of the k-flow graph double cover conjecture, the 5-cycle double cover conjecture, the cycle double cover conjecture has an oriented version.

k-flow graph double cover conjecture (oriented version):
Suppose G is a bridgeless graph and 2 <= k <= 5 is an integer. Then there are (7-k) directed graphs H_1, H_2, ..., H_{7-k}, each being an orientation of a subgraph of G,  such that each H_i admits a positive k-flow graph and each edge of G occurs in exactly two of the H_i's, once in each direction.

5-cycle double cover conjecture (oriented version):
Each bridgeless graph has a directed 5-cycle double cover, i.e. G has 5 directed cycles, their union covers each edge exactly twice, once in each direction.

 The oriented 5-cycle double cover conjecture is due to Archdeacon [Ar84] and Jaeger [Ja88].

For a detailed discussion of (oriented or unoriented) cycle double cover conjecture, 5-cycle double cover conjecture, and 5-flow conjecture, see CQ's book [Zh97].

Weaker version of k-flow graph double cover conjecture

For k=2, 3, 4, 5, there is a weaker version of k-flow graph double cover. Namely, we drop off the requirement on the number of subgraphs.

k-flow graph double conjecture (weaker unoriented version)                                                         Suppose G is a bridgeless graph. Then G has a family of subgraphs, each being a k-flow graph, and their union covers each edge of G exactly twice.

k-flow graph double conjecture (weaker oriented version)                                                                  Suppose G is a bridgeless graph. Then there is a family of directed graphs, each being an orientation of a subgraph of G, and each admist a positive k-flow, such that  their union covers each edge of G exactly twice, once in each direction.

It follows from the definition that for k=2, 3, 4,  weaker (oriented or unoriented) version k-flow graph double conjecture implies the weaker (oriented or unoriented) version (k+1)-flow graph double cover conjecture.  So among all the above conjectures, the weakest one is the following:

Each bridgeless graph G has a family of subgraphs, each admist a nowhere zero 5-flow, and their union covers each edge of G exactly twice. 

The k=2 case of the weaker version of k-flow graph double cover conjecture are known as cycle double cover conjecture.

Double cycle cover conjecture (unoriented version):
Each bridgeless graph has a cycle double cover, i.e. G has a family of cycles, their union covers each edge exactly twice.

Double cycle cover conjecture (oriented version):
Each bridgeless graph has a oriented cycle double cover, i.e. G has a family of directed cycles, their union covers each edge exactly twice, once in each direction.

The unoriented version of the double cycle cover conjecture  is due to Seymour [Sey79] and Szekeres [Sz73]. The oriented version is due to Jaeger [Ja88].

References

[Ar84] D. Archdeacon, Face coloring of embedded graphs. J. Graph Theory, 8(1984), 387-398.

[Ce84] U.A.Celmins,  On cubic graphs that do not have an edge 3-coloring. Ph.D. Thesis, University of Waterloo, Waterloo, Canada, (1984).

[Ja88]  F. Jaeger, Nowhere zero flow problems. Selected Topics in Graph Theory 3 (L.W.Beineke and R.J.Wilson eds.), Academic Press, London (1988), 71-95.

[Pr81]  M. Pressmann, Sur les colorations des aretes des graphes cubiques. These de Doctorat de 3^{eme}, Grenoble, (1981).

{Sey79]  P.D.Seymour, Sums of circuits. Graph Theory and Related Topics (J.A.Bondy and U.S.R.Murty, eds.),
Academic Press, New York, (1979), 342-255.

[Sz73] G. Szekeres,  Polyhedral decompositions of cubic graphs. Bull. Austral. Math. Soc., 8(1973), 367-387.

[Tu54]  W.T.Tutte, A contribution on the theory of chromatic polynomial. Canad. J. Math., 6(1954), 80-91.

[Zh97]  C.Q.Zhang,  Integer flows and cycle covers of graphs. Marcel Dekker, Inc., 1997.