Is it true that whenever D is a directed graph on n nodes with minimum out-degree at least [math]n/k[/math], then D has a directed cycle of length at most k?
This conjecture was formulated by Caccetta and Häggkvist  in 1978. For a survey, see . The k=2 case is trivial, but the k=3 case is already open: is it true that a directed graph on [math]n[/math] nodes with minimum out-degree at least [math]n/3[/math] always contains a directed triangle? The weaker version where all in-degrees and out-degrees are at least [math]n/3[/math] is also open.
There are several interesting partial results:
- the conjecture is true if D has independence number 2 
- the conjecture is true if the subgraph induced by the in-neighbours of any node is a tournament 
- a digraph with minimum out-degree at least [math]0.3465 n[/math] contains a directed triangle .
- L. Caccetta, R. Häggkvist, On minimal digraphs with given girth, Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), pp. 181-187, Congress. Numer., XXI, Utilitas Math., Winnipeg, Man., 1978.
- B. D. Sullivan, A Summary of Results and Problems Related to the Caccetta-Häggkvist Conjecture, ARCC-AIM Workshop on the Caccetta-Häggkvist Conjecture, 2006, arXiv link
- N. Lichiardopol, Proof of the Caccetta–Häggkvist conjecture for oriented graphs with positive minimum out-degree and of independence number two, DOI link
- N. Lichiardopol, Proof of the Caccetta-Häggkvist conjecture for in-tournaments with respect to the minimum out-degree, and pancyclicity, pdf link
- J. Hladky, D. Král, S. Norine, Counting flags in triangle-free digraphs, arXiv link