Originators: Louis Caccetta and Roland Häggkvist (presented by Kostochka - REGS 2007)
Conjecture 1: [CH] An n-vertex oriented graph with minimum outdegree at least n/r has a directed cycle of length at most r.
Comments: The main problem is to prove Conjecture 1 for r = 3. Numerous papers have studied values α and c such that minimum outdegree at least αn or at least n/3+c forces a 3-cycle. The aim is to reduce α to 1/3 or c to 0. Results have been proved by Caccetta-Häggkvist [CH], Bondy [B], Chvátal-Szemerédi, Nishimura [N], Shen [S1,S2] (both types), and Hamburger-Haxell-Kostochka [HHK] (see also [dSS] and [Su]). The result of [HHK] is that minimum outdegree 0.35312n forces a directed 3-cycle. A related conjecture would improve the known results.
Conjecture 2 (Chudnovsky-Seymour-Sullivan [CSS]): If an oriented graph G without 3-cycles arises from a tournament by deleting k edges, then deletion of at most k/2 additional edges will break all cycles in G.
Comments: Chudnovsky-Seymour-Sullivan [CSS] gave a fairly short proof that deleting k additional edges suffices.
References:
[B] Bondy, J. A.; Counting subgraphs: a new approach to the
Caccetta-Häggkvist conjecture. Graphs and combinatorics (Marseille, 1995).
Discrete Math. 165/166 (1997), 71--80.
[CH] L. Caccetta and R. Häggkvist; On minimal digraphs with given girth.
Congressus Numerantium, XXI, 1978.
[CSS] Chudnovsky, Maria; Seymour, Paul; Sullivan, Blair;
Cycles in dense digraphs. Combinatorica 28 (2008), no. 1, 1--18.
[dSS] de Graaf, M.; Schrijver, A.; Seymour, P. D.; Directed triangles in
directed graphs. Discrete Math. 110 (1992), no. 1-3, 279--282.
[HHK] Hamburger, Peter; Haxell, Penny; Kostochka, Alexandr;
On directed triangles in digraphs.
Electron. J. Combin. 14 (2007), no. 1, Note 19, 9 pp.
[S1] Shen, Jian; Directed triangles in digraphs, J. Combin. Theory (B), 74
(1998), 405--407.
[S2] Shen, Jian; On the Caccetta-Häggkvist conjecture. Graphs Combin. 18
(2002), no. 3, 645--654.
[Su] Sullivan, B.; A summary of results and problems related to the
Caccetta--Häggkvist conjecture, manuscript, 2006.