We show that every directed graph with minimum out-degree at least 18k contains at least k vertex disjoint cycles. This is an improvement over the result of Alon who showed this result for digraphs of minimum out-degree at least 64k. The main benefit of the argument is that getting better results for small values of k allows for further improvements to the constant.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Directed graph
- Disjoint cycles
- Minimal out-degree