HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Hoàng-Reed conjecture holds for tournaments

Frédéric Havet 1 Stéphan Thomassé 1 Anders Yeo 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Hoàng-Reed conjecture asserts that every digraph $D$ has a collection $\cal C$ of circuits $C_1,\dots,C_{\delta ^+}$, where $\delta ^+$ is the minimum outdegree of $D$, such that the circuits of $\cal C$ have a forest-like structure. Formally, $|V(C_i)\cap (V(C_1)\cup \dots \cup V(C_{i-1}))|\leq 1$, for all $i=2,\dots ,\delta^+$. We verify this conjecture for the class of tournaments.
Document type :
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, September 15, 2006 - 11:22:26 AM
Last modification on : Friday, February 4, 2022 - 3:09:17 AM
Long-term archiving on: : Monday, September 20, 2010 - 4:22:13 PM


  • HAL Id : inria-00091366, version 2


Frédéric Havet, Stéphan Thomassé, Anders Yeo. Hoàng-Reed conjecture holds for tournaments. [Research Report] RR-5976, INRIA. 2006, pp.7. ⟨inria-00091366v2⟩



Record views


Files downloads