The linear cycle-and-edge cover conjecture for 2-regular graphs

Let GG be an nn-vertex graph. A cycle-and-edge cover is a cover of the edge set of GG by subgraphs that are 22-regular graphs or single edges. The linear cycle-and-edge cover conjecture. For all nn-vertex graphs GG, the minimum number of such subgraphs satisfies

fre(G)=O(n).\operatorname{f_{re}}(G)=O(n).

This is presented as a weakened version of the paper's main conjecture, replacing decompositions into cycles and edges by decompositions into 22-regular graphs and edges. The supplied text does not state a resolution.

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).

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.