The regular linear cycle-and-edge cover conjecture

From papers

Let GG be an nn-vertex (2k+1)(2k+1)-regular graph, where kk is a nonnegative integer. Let fre(G)\operatorname{f_{re}}(G) denote the minimum number of 22-regular graphs and edges in a cover of the edges of GG. The regular linear cycle-and-edge cover conjecture. For all nn-vertex (2k+1)(2k+1)-regular graphs GG,

fre(G)n1.\operatorname{f_{re}}(G)\leq n-1.

This is proposed as a special case of the preceding linear bound conjecture; Petersen's 22-factor theorem is cited as reducing the regular case to odd-regular graphs. The supplied text gives no resolution, though it notes the claim is easy for odd-regular graphs with a perfect matching.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Saieed Akbari, Jonny Aloni, Arash Beikmohammadi and Alexander Clow, “Tight Bounds for Cycle-Edge Decompositions and Covers”, arXiv:2509.01901 (2025).

Solutions 0

No solutions have been posted yet.