# Caccetta-Häggkvist conjecture

From Egres Open

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*?

## Remarks

This conjecture was formulated by Caccetta and Häggkvist ^{[1]} in 1978. For a survey, see ^{[2]}. 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^{[3]} - the conjecture is true if the subgraph induced by the in-neighbours of any node is a tournament
^{[4]} - a digraph with minimum out-degree at least [math]0.3465 n[/math] contains a directed triangle
^{[5]}.

See also: Caccetta-Häggkvist conjecture at Open Problem Garden.

## References

- ↑ 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