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?
The reverse is true by a result of Kotzing : 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 . Note that the Bipartizing matching conjecture in this paper has been disproved by Hoffmann-Ostenhof , who also offered a modified version.
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