Sabidussi's compatibility conjecture

From Egres Open
Jump to: navigation, search

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

Compatible Euler-tours

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

References

  1. A. Kotzig, Moves without forbidden transitions in a graph, EUDML link
  2. H. Fleischner, Bipartizing matchings and Sabidussi's compatibility conjecture, DOI link
  3. A. Hoffmann-Ostenhof, A counterexample to the bipartizing matching conjecture, DOI link