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 in the same 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 in the same 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.
(A previous version of this page stated the conjecture incorrectly)
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
