# Sabidussi's compatibility conjecture

Let *G=(V,E)* be an Eulerian graph with minimum degree at least 4, and let *W* be a closed Eulerian walk of *G*. Is it true that *G* has a cycle decomposition such that no pair of consecutive edges of *W* appear consecutively in any cycle of the decomposition?

## Remarks

The reverse is true by a result of Kotzing ^{[1]}: Given a cycle decomposition of *G*, there always exists a closed Eulerian walk *W* such that no pair of consecutive edges of *W* appear consecutively in any cycle of the decomposition. The relation of the conjecture to several others (in particular to the Cycle double cover conjecture) is explained in ^{[2]}. Note that the Bipartizing matching conjecture in this paper has been disproved by Hoffmann-Ostenhof ^{[3]}, who also offered a modified version.

## Related conjectures

This conjecture is also related to several others described at Open Problem Garden:

- Decomposing eulerian graphs
- Cycle double cover conjecture
- Faithful cycle covers
- Nowhere-zero 5-flow conjecture