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
2 Department of Computer Science

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.

Mots clés: tournament; forest-like structure; circuit

Domaines: Mathématique discrète [cs.DM]

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⟩