Decomposing eulerian graphs
Definition: Let be an Eulerian graph and for every vertex , let be a partition of the edges incident with . We call a transition system. If every member of has size at most (for every ), then we call a -transition sytem. A compatible decomposition of is a list of edge-disjoint cycles with union so that every contains at most one edge from every member of .
Let be a graph and let be the graph obtained from by replacing each edge of G by two edges in parallel. Let be the 2-transition system of with whenever and are incident with . Now, is an Eulerian graph and every compatible decomposition of gives a cycle double cover of . 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.
We define a transition system to be admissable if every member of contains no more than half of the edges in any edge-cut. It is easy to see that if there is a compatible decomposition of , then must be admissable. The converse of this is not true; There is an admissable 2-transition system of the graph which does not admit a compatible decomposition. Recently, G. Fan and C.Q. Zhang [FZ] have proved that does have a compatible decomposition whenever is admissable and has no minor. This result imporoved upon an earlier theorem of Fleischner and Frank [FF]. Very recently, I have proved a weak version of the above conjecture, by showing that also has a compatible decomposition when P is a 2-transition system and G is 80-edge-connected. I'd quite like to see an improvement on this bound. Here is a related conjecture.
If is given by then we may form a 2-transition system by putting in for every (working modulo ). Now a compatible decomposition of is precisely a cycle decomposition of satisfying the above conjecture. Thus, Sabidussi's conjecture is equivalent to the assertion that has a compatible decomposition whenever has no vertex of degree two and is a 2-transition system which comes from an Euler tour.
Let be a directed Eulerian graph and for every vertex , let be a partition of the edges incident with into pairs so that every in-edge is paired with an out-edge. We define a compatible decomposition to be a decomposition of into directed circuits so that every directed circuit contains at most one edge from every member of . Our current techniques don't seem to shed any light on the problem of finding compatible decompositions for Eulerian digraphs. Next I pose a very basic question which is still open.