← All problems

Sabidussi's compatibility conjecture

36 years old · traced to

Let G=(V,E)G=(V,E) be a finite connected multigraph, allowing loops and parallel edges, and suppose every vertex has even degree and deg⁡G(v)≥4\deg_G(v)\ge 4 for all v∈Vv\in V. Let W=e1e2⋯emW=e_1e_2\cdots e_m be a closed trail traversing each edge of GG exactly once, where m=∣E∣m=|E|; regard its edge order cyclically, so eme_m and e1e_1 are consecutive. A circuit is a nonempty connected 22-regular subgraph, and a circuit decomposition is a partition of EE into circuits. Is there a circuit decomposition of GG in which, for every ii (with indices modulo mm), the edges eie_i and ei+1e_{i+1} 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 HH, let 2H2H 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 HH has a circuit double cover if and only if 2H2H 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

Never refreshed

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.