Enomoto–Kaneko–Tuza conjecture for edge-disjoint cycle covers in digraphs

Let GG be a digraph on nn vertices. Its minimum semi-degree is the minimum, over all vertices, of the smaller of its indegree and outdegree. A collection of cycles is edge-disjoint if no directed edge belongs to more than one cycle, and it covers V(G)V(G) if every vertex lies on one of the cycles.

Directed edge-disjoint cycle-cover conjecture. For every kNk\in\mathbb{N} with k2k\geq 2, if the minimum semi-degree of GG is at least n/kn/k, then V(G)V(G) can be covered by k1k-1 edge-disjoint cycles.

This is proposed as a directed analogue of the Enomoto–Kaneko–Tuza conjecture for graphs. The paper proves the assertion for regular digraphs through its main theorem, while the general digraph statement remains open in the source.

Sources & referencesView supporting material

Primary source

Allan Lo, Viresh Patel and Mehmet Akif Yıldız, “Cycle Partitions in Dense Regular Digraphs and Oriented Graphs”, arXiv:2309.11677 (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.