Hoàng-Reed Conjecture

Importance: High ✭✭✭
Recomm. for undergrads: no
Posted by: fhavet
on: March 11th, 2013
Conjecture   Every digraph in which each vertex has outdegree at least $ k $ contains $ k $ directed cycles $ C_1, \ldots, C_k $ such that $ C_j $ meets $ \cup_{i=1}^{j-1}C_i $ in at most one vertex, $ 2 \leq j \leq k $.

This conjecture is not even known to be true for $ k=3 $. In the case $ k=2 $, 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.


*[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.