**Sabidusi’s**** Compatibility
Conjecture **

A *cycle* in a graph is
a simple closed walk. The following is known as Sabidusi’s
Compatibility Conjecture.** **

**Conjecture:** *Given an Eulerian
trail *T* in a graph *G*,
there exists a partition of the edges of *G*
into cycles such that consecutive edges in *T* lie in different cycles. *

The conjecture, if true, implies the cycle double cover conjecture. See [F1] and [F2] for details on this relation.

The following *Faithful Decomposition Conjecture*
is more general.

**Conjecture:** *Let* G *be a 6-edge-connected Eulerian
graph and let* P_1 *be any partition of the edges of* G *into cycles.
Then there exists a partition *P_2 *of the edges of* G *into cycles
such that no pair of edges are consecutative
in both* P_1 *and* P_2.

The requirement of 6-edge-connected is necessary, as seen by the example
where edges in a perfect matching of the Petersen Graph are doubled and the
partition *P_1* of the resulting graph has five 2-cycles and two 5-cycles.

**References:**

[F1] H. Fleischner,
“Eulerian graphs and related topics Vol 1”, Ann. Discrete Math **45**, North-Holland,

[F2] H. Fleischner,
“Eulerian graphs and related topics Vol 2”, Ann. Discrete Math **50**, North-Holland,

Submitted
by: Dan Archdeacon, Department of Mathematics and Statistics,

Send comments to *dan.archdeacon@uvm.edu*

December 2003