2020/11/23 by Steiner, Raphael
#05C07 #05C20 #05C38 #05C40 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2011.11605
A conjecture by Lichiardopol states that for every k ≥ 1 there exists an integer g(k) such that every digraph of minimum out-degree at least g(k) contains k vertex-disjoint directed cycles of pairwise distinct lengths. Motivated by Lichiardopol's conjecture, we study the existence of vertex-disjoint directed cycles satisfying length constraints in digraphs of large connectivity or large minimum degree. Our main result is that for every k ∈ ℕ, there exists s(k) ∈ ℕ such that every strongly s(k)-connected digraph contains k vertex-disjoint directed cycles of pairwise distinct lengths. In contrast, for every k ∈ ℕ we construct a strongly k-connected digraph containing no two vertex- or arc-disjoint directed cycles of the same length. It is an open problem whether g(3) exists. Here we prove the existence of an integer K such that every digraph of minimum out- and in-degree at least K contains 3 vertex-disjoint directed cycles of pairwise distinct lengths.