(m,n)cycle covers
\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph has a (5,2)cyclecover. \end{conjecture}
Definition: If $G=(V,E)$ is a graph, a binary cycle of $G$ is a set $C \subseteq E$ such that every vertex of the graph $(V,C)$ has even degree. An $(m,n)$cyclecover of $G$ is a list $L$ consisting of $m$ cycles so that every edge of $G$ is contained in exactly $n$ of these cycles.
Since every binary cycle can be written as a disjoint union of edge sets of ordinary cycles, the above conjecture is a strengthening of the cycle double cover conjecture. For positive integers $m,n$ it is natural to ask what family of graphs have $(m,n)$cyclecovers. The following chart gives some information about this question for small values of $m$ and $n$. A "yes" in the $(m,n)$ box indicates that every graph with no cutedge has an $(m,n)$cyclecover. A "no" indicates that no graph has an $(m,n)$cyclecover. A more detailed explanation of the entries in this chart appears below it.
m  
n 

We did not include odd values of n, since any graph with an $(m,n)$cyclecover for an odd integer $n$ must be \Def[Eulerian]{eulerian graph}. The entry "NZ 4flow" is short for \Def[nowherezero]{nowherezero flows} 4flow. Thus, our chart indicates that ($G$ has a nowherezero 4flow) if and only if ($G$ has a $(3,2)$cyclecover) if and only if ($G$ has a $(4,2)$cyclecover). These equivalences were discovered by Tutte [Tu].
Two of the $(m,n)$ boxes are conjectures. The 5CDC conj is the 5 cycle double cover conjecture and the BF conjecture is the \OPref[BergeFulkerson conjecture]{the_berge_fulkerson_conjecture}. In both of these cases, the conjecture is equivalent to the assertion that every graph with no cutedge has an $(m,n)$cyclecover (i.e. it would be accurate to put a "yes" in the corresponding. box). For emphasis, we state the BergeFulkerson conjecture again below in this new form.
\begin{conjecture}[The BergeFulkerson conjecture] Every graph with no cutedge has a (6,4)cyclecover. \end{conjecture}
The fact that the above conjecture is equivalent to the usual statement of the BergeFulkerson conjecture was discovered by Jaeger [J]. For cubic graphs this equivalence is easy to see, since $M_1,\ldots,M_6$ satisfy the BergeFulkerson conjecture if and only if $E\M_1,\ldots,E\M_6$ is a $(6,4)$cyclecover. By Jaeger's argument, the weak BergeFulkerson conjecture is equivalent to the statement that there exists a fixed integer $k$ so that every bridgeless graph has a $(3k,2k)$cyclecover.
A postman set is a set of edges $J$ such that $E(G)\J$ is a cycle. The entry "k post. sets" in the $(k,k1)$ box of the above chart indicates that a graph G has a $(k,k1)$cyclecover if and only if it is possible to partition the edges of $G$ into $k$ postman sets. This equivalence follows immediately from the definition. Rizzi's Packing postman sets conjecture is thus equivalent to the following conjecture on cyclecovers.
\begin{conjecture}[the packing postman sets conjecture] If every odd edgecut of $G$ has size $\ge 2k+1$, then $G$ has a $(2k+1,2k)$cyclecover. \end{conjecture}
Next we turn our attention to orientable cycle covers. If $H$ is a directed graph a map $\phi:E(H) \rightarrow \{1,0,1\}$ is a 2flow or an oriented cycle if at every vertex of $H$, the sum of $\phi$ on the incoming edges is equal to the sum of $\phi$ on the outgoing edges. It is easy to see that the support of a 2flow is always a cycle. Furthermore, for any oriented cycle, there is a list $L$ of edgedisjoint circuits with directions so that an edge $e$ is forward (backward) in a circuit of $L$ if and only if $\phi(e)=1$ ($\phi(e)=1$). So as in the unoriented case, an oriented cycle may be viewed as the edgedisjoint union of oriented circuits. For an even integer $n$, a $(m,n)$orientedcyclecover of a graph $G$ is a list of $m$ oriented cycles so that every edge of $G$ appears as a forward edge $n/2$ times and a backward edge $n/2$ times. The following conjecture is the common generalization of the orientable cycle double cover conjecture and the five cycle double cover conjecture. It is due to Archdeacon and Jaeger.
\begin{conjecture}[The orientable five cycle double cover conjecture] Every graph without a cutedge has a (5,2)orientedcyclecover. \end{conjecture}
Considerably less is known about $(m,n)$orientedcyclecovers. We sumarize some of what is known for small values of $m$ and $n$ below.
m  
n 

Every graph with an $(m,n)$cyclecover also has a $(2m,2n)$orientedcyclecover obtained by taking two copies of each cycle with opposite orientations. Thus, by Bermond, Jackson, and Jaeger's $(7,4)$cyclecover theorem, every bridgeless graph with no has a $(14,8)$orientedcyclecover. DeVos and Goddyn have observed that Seymour's 6flow theorem can be used to construct an $(11,6)$orientedcyclecover for every bridgeless graph. By combining these, we find that for every even integer $n \ge 10$ there exists an $m$ so that every bridgeless graph has an $(m,n)$orientedcyclecover. This question is still open for $n=2,4,10$.
The following conjecture appears in the above chart. \begin{conjecture}[The orientable eight cycle four cover conjecture] Every graph with no cutedge has a (8,4)orientedcyclecover. \end{conjecture}
This conjecture may be viewed as a sort of oriented version of the BergeFulkerson conjecture. To see this analogy, note that ($G$ has a nowherezero 4flow) if and only if ($G$ has a $(3,2)$cyclecover) if and only if ($G$ has a $(4,2)$orientedcyclecover). The BergeFulkerson conjecture and the above conjecture assert respectively that every bridgeless graph has a $(6,4)$cyclecover and a $(8,4)$orientedcyclecover (i.e. a cover with double the parameters which are equivalent to a nowherezero 4flow). As with most of the conjectures in this area, the above conjecture is trivially true for graphs with nowherezero 4flows and it holds for the Petersen graph.
Bibliography
[A] D. Archdeacon, Face coloring of embedded graphs. J. Graph Theory, 8(1984), 387398.
[BJJ] J.C. Bermond, B. Jackson, and F. Jaeger, Shortest covering of graphs with cycles, J. Combinatorial Theory Ser. B 35 (1983), 297308. \MRhref{0735197}
*[C] A. U. Celmins, On cubic graphs that do not have an edge3colouring, Ph.D. Thesis, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada, 1984.
[F] G. Fan, Integer flows and cycle covers, J. Combinatorial Theory Ser. B 54 (1992), 113122. \MRhref{1142267}
[J] F. Jaeger, Flows and Generalized Coloring Theorems in Graphs, J. Combinatorial Theory Ser. B 26 (1979) 205216. \MRhref{0532588}
[J88] F. Jaeger, Nowhere zero flow problems. Selected Topics in Graph Theory 3 (L.W.Beineke and R.J.Wilson eds.), Academic Press, London (1988), 7195.
*[P] M. Preissmann, Sur les colorations des arêtes des graphes cubiques, Thèse de 3ème cycle, Grenoble (1981) .
[T54] W.T. Tutte, A Contribution on the Theory of Chromatic Polynomials, Canad. J. Math. 6 (1954) 8091. \MRhref{0061366}
[T66] W.T. Tutte, On the Algebraic Theory of Graph Colorings, J. Combinatorial Theory 1 (1966) 1550. \MRhref{0194363}
* indicates original appearance(s) of problem.