Home » Subject » Graph Theory » Directed Graphs

Hoàng-Reed Conjecture

Importance: High ✭✭✭
Author(s): Hoang, Chinh T.
Reed, Bruce A.
Subject: Graph Theory
» Directed Graphs
Keywords:
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.

Related problems

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.
add new comment