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
