Sabidussi's compatibility conjecture
Let be a finite connected multigraph, allowing loops and parallel edges, and suppose every vertex has even degree and for all . Let be a closed trail traversing each edge of exactly once, where ; regard its edge order cyclically, so and are consecutive. A circuit is a nonempty connected -regular subgraph, and a circuit decomposition is a partition of into circuits. Is there a circuit decomposition of in which, for every (with indices modulo ), the edges and belong to different circuits? Ulyanov, arXiv:2607.13225 (preprint) Fleischner, Genest, and Jackson (2006)
Background
Sabidussi’s conjecture dates to 1975 and was recorded by Fleischner. Its language can be expressed using transitions: at each passage through a vertex, the Euler tour pairs the half-edge on which it arrives with the half-edge on which it departs. Compatibility means that no circuit in the decomposition uses any of these prescribed pairs. This is distinct from finding a compatible Euler tour: Kotzig’s result says that a partial transition system on an Eulerian graph admits a compatible Euler tour if and only if every vertex at which transitions are prescribed has degree at least four, while compatible circuit decompositions are a harder problem. Fleischner, Genest, and Jackson (2006) Ulyanov, arXiv:2607.13225 (preprint)
The broader problem of characterizing compatible circuit decompositions has a connection with the circuit double cover conjecture. For a graph , let denote the graph formed by replacing each edge by two parallel copies, and prescribe the transition system that pairs those copies. The 2006 paper states that has a circuit double cover if and only if has a circuit decomposition compatible with that transition system. This is a connection to the broader compatibility problem, not a consequence attributed here to Sabidussi’s conjecture itself. Fleischner, Genest, and Jackson (2006)
References
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.