Caccetta-Häggkvist conjecture

From Egres Open
Jump to: navigation, search

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

  1. 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.
  2. 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
  3. N. Lichiardopol, Proof of the Caccetta–Häggkvist conjecture for oriented graphs with positive minimum out-degree and of independence number two, DOI link
  4. N. Lichiardopol, Proof of the Caccetta-Häggkvist conjecture for in-tournaments with respect to the minimum out-degree, and pancyclicity, pdf link
  5. J. Hladky, D. Král, S. Norine, Counting flags in triangle-free digraphs, arXiv link