Arc-disjoint directed cycles in regular directed graphs
Status open medium confidence
The conjecture that every $k$-regular directed graph with no parallel arcs contains $\binom{k+1}{2}$ arc-disjoint directed cycles remains open. The best known lower bound continues to be Alon's 1996 result of $\frac{1}{128}k^2$ arc-disjoint directed cycles in any digraph with minimum outdegree at least $k$, and no post-2013 paper improving this constant or proving the conjecture was found.
Reviewer notes. All six search queries were exhausted without finding a post-2013 paper specifically improving the arc-disjoint cycles bound in k-regular digraphs. The arXiv paper 1701.06364 (Bucić, 2018) improves the constant for vertex-disjoint cycles under minimum outdegree conditions (reducing 64k to 18k for guaranteeing k vertex-disjoint cycles), but addresses a different problem. The 2026 paper 2604.13700 (Steiner) concerns openly disjoint cycles and directed tree-width in regular digraphs, not arc-disjoint cycles. The ScienceDirect page for the 2020 Discrete Mathematics paper on disjoint directed cycles returned HTTP 403. Confidence is medium rather than high because the ScienceDirect paper (pii/S0012365X20301199) could not be verified and might contain relevant partial results.
Discussion
If true, $ {k+1 \choose 2} $ would be best possible as shown by the complete symmetric digraph. Alon et al. [AMM] showed that a $ k $ -regular directed graph with no parallel arcs contains at least $ \frac{3}{2^{19}}k^2 $ arc-disjoint directed cycles. It was then improved by Alon [A] who showed that every directed graph with minimum outdegree at least $ k $ contains at least $ \frac{1}{128}k^2 $ arc-disjoint directed cycles.
Bibliography
-
[?][A} N. Alon, Disjoint directed cycles, J. Combinatorial Theory, Ser. B, 68 (1996), 167-178. -
★
[AMM]N. Alon, C. McDiarmid and M. Molloy, Edge-disjoint cycles in regular directed graphs, J. Graph Theory, 22 (1996), no. 3, 231-237.