Directed regular graph cycle-cover conjecture

Let GG be a directed dd-regular graph on nn vertices, and regard a cycle as a directed cycle, with an individual edge allowed to count as a cycle of length two as in the source. Directed cycle-cover conjecture. Every directed dd-regular nn-vertex graph has a collection of O(n/d)\mathcal O(n/d) vertex-disjoint cycles that cover all vertices of the graph. This is presented as a potential generalisation of the Feige–Fuchs conjecture; it remains open.

Sources & referencesView supporting material

Primary source

Micha Christoph, Nemanja Draganić, António Girão, Eoin Hurley, Lukas Michel and Alp Müyesser, “New bounds for linear arboricity and related problems”, arXiv:2507.20500 (2025).

Additional references

3 papers in this index state this conjecture (2012–2025). The statement above is taken from the most recent of them; the others are arXiv:2010.11664, arXiv:1201.4326.

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.