Caccetta-Haggkvist conjecture is a longstanding open problem on degree conditions that force an oriented graph to contain a directed cycle of a bounded length. Motivated by this conjecture, Kelly, Kuhn and Osthus initiated a study of degree conditions forcing the containment of a directed cycle of a given length. In particular, they found the optimal minimum semidegree, i.e., the smaller of the minimum indegree and the minimum outdegree, that forces a large oriented graph to contain a directed cycle of a given length not divisible by $3$, and conjectured the optimal minimum semidegree for all the other cycles except the directed triangle. In this paper, we establish the best possible minimum semidegree that forces a large oriented graph to contain a directed cycle of a given length divisible by $3$ yet not equal to $3$, hence fully resolve the conjecture of Kelly, Kuhn and Osthus. We also find an asymptotically optimal semidegree threshold of any cycle with a given orientation of its edges with the sole exception of a directed triangle.
تحميل البحث