![](/files/happy5.png)
Hoàng-Reed Conjecture
Conjecture Every digraph in which each vertex has outdegree at least
contains
directed cycles
such that
meets
in at most one vertex,
.
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ C_1, \ldots, C_k $](/files/tex/0df670e43d33838d6e04e86a590da56100880e60.png)
![$ C_j $](/files/tex/b1365660549601f059d1b19f13f120a8fd821c25.png)
![$ \cup_{i=1}^{j-1}C_i $](/files/tex/b45609a301fcc110ef904d9f320f045d3947da71.png)
![$ 2 \leq j \leq k $](/files/tex/f4a8b4068d7bbb76eee5a6457f5fa87ff65184f1.png)
This conjecture is not even known to be true for . In the case
, Thomassen proved [T] that every digraph with minimum outdegree 2 has two directed cycles intersecting on a vertex.
This conjecture would imply the Caccetta-Häggkvist Conjecture.
Bibliography
*[HR] C.T. Hoàng and B. Reed, A note on short cycles in digraphs, Discrete Math., 66 (1987), 103-107.
[T] C. Thomassen, The 2-linkage problem for acyclic digraphs, Discrete Math., 55 (1985), 73-87.
* indicates original appearance(s) of problem.