**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 *2r ^{2}-3r+1*, then the
digraph has a cycle of length at most the ceiling of

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.