← All problems

Equivalence of the 3/5 and 2/5 5-cycle double cover bounds

1 year old · traced to

Let GG be a bridgeless graph, and let a 55-cycle double cover be a collection C=(E0,…,E4){\cal C}=(E_0,\ldots,E_4) of five cycles in which every edge belongs to exactly two cycles. Equivalence conjecture for strengthened 5-cycle double covers. The conjecture asserting that every bridgeless graph admits such a cover with

∣E0∣≥35∣E(G)∣|E_0|\geq \frac{3}{5}|E(G)|

is equivalent to the conjecture asserting that every bridgeless graph admits such a cover with

∣E0∣≥25∣E(G)∣.|E_0|\geq \frac{2}{5}|E(G)|.

The paper says that the 2/52/5 formulation is equivalent to the ordinary 5-cycle double cover conjecture and proposes the equivalence with the strengthened formulation. It remains open.

References
  1. Giuseppe Mazzuoccolo and Vahan Mkrtchyan, “Expanding vertices to triangles in cubic graphs”, arXiv:2504.19201 (2025).

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.