Caccetta-Häggkvist Conjecture (1978)

Originator(s): L. Caccetta and R. Häggkvist [CH] (See here for another presentation.)

Conjecture: Every simple directed n-vertex graph with minimum outdegree at least r has a cycle with length at most the ceiling of n/r.

Comments/Partial results: The conjecture was proved for r=2 in [CH], for r=3 by Hamidoune [H2], and for r=4 and r=5 by Ho`ang and Reed [HR]. In general, Shen [S2] proved the conjecture for r <= \sqrt(n/2). That is, if every vertex has outdegree at least r and the number n of vertices is at least 2r2-3r+1, then the digraph has a cycle of length at most the ceiling of n/r.

Another approach is to force a cycle of length at most (n/r)+c for some small c. This was proved for c=2500 by Chvátal and Szemer'edi [CS], for c=304 by Nishimura [N], and for c=73 by Shen [S3].

The case r=n/2 is trivial, but r=n/3 has received much attention. If Seymour's second neighborhood conjecture is true, then all digraphs with minimum indegree and outdegree at least n/3 (and no cycles of length at most two) have 3-cycles. That is, a successor of x would have to have a successor that is a predecessor of x.

Meanwhile, research has sought lower bounds on c such that minimum outdegree at least cn in an n-vertex simple digraph would force a 3-cycle. Caccetta and Häggkvist [CH] proved that c <= (3-\sqrt5)/2 = .382. Bondy [Bo] proved that c <= (2\sqrt6-3)/5 = .379. Shen [S1] proved that c <= 3-\sqrt7 = .354.

A digraph is r-regular if every vertex has indegree and outdegree r. Behzad, Chartrand, and Wall [BCW] conjectured that the minimum number of vertices in an r-regular digraph with girth g is r(g-1)+1. Their example achieving this consisting of r(g-1)+1 vertices on a circle with each vertex having edges to the next r vertices in clockwise order. The conjecture was proved for r=2 by Behzad [Beh], for r=3 by Bermond [Ber], and for vertex-transitive graphs by Hamidoune [H1]. The full conjecture follows immediately from the Caccetta-Häggkvist Conjecture.

References:
[Beh] Behzad, M. Minimal 2-regular digraphs with given girth. J. Math. Soc. Japan 25 (1973), 1--6.
[BCH] Behzad, M.; Chartrand, G.; Wall, C. E. On minimal regular digraphs with given girth. Fund. Math. 69 1970 227--231.
[Ber] Bermond, J.-C. 1-graphes re'guliers minimaux de girth donne'. Colloque sur la The'orie des Graphes (Paris, 1974). Cahiers Centre E'tudes Recherche Ope'r. 17 (1975), no. 2-4, 125--135.
[Bo] 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] Caccetta, Louis; Ha"ggkvist, R. 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.
[CS] Chvátal, V.; Szemere'di, E. Short cycles in directed graphs. J. Combin. Theory Ser. B 35 (1983), no. 3, 323--327.
[H1] Hamidoune, Y. O. Quelques proble`mes de connexite' dans les graphes oriente's. J. Combin. Theory Ser. B 30 (1981), no. 1, 1--10.
[H2] Hamidoune, Y. O. A note on minimal directed graphs with given girth. J. Combin. Theory Ser. B 43 (1987), no. 3, 343--348.
[HR] Ho`ang, C. T.; Reed, B. A note on short cycles in digraphs. Discrete Math. 66 (1987), no. 1-2, 103--107.
[N] Nishimura, T. Short cycles in digraphs. Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986). Discrete Math. 72 (1988), no. 1-3, 295--298.
[S1] Shen, J. Directed triangles in digraphs. J. Combin. Theory Ser. B 74 (1998), no. 2, 405--407.
[S2] Shen, J. On the girth of digraphs. Discrete Math. 211 (2000), no. 1-3, 167--181.
[S3] Shen, J. On the Caccetta-Ha"ggkvist conjecture. Graphs Combin. 18 (2002), no. 3, 645--654.

Back to Index Page Link to Glossary