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 , 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.
Type de document :
Rapport
[Research Report] RR-5976, INRIA. 2006, pp.7
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00091366
Contributeur : Rapport de Recherche Inria <>
Soumis le : vendredi 15 septembre 2006 - 11:22:26
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : lundi 20 septembre 2010 - 16:22:13

Fichier

Identifiants

  • HAL Id : inria-00091366, version 2

Citation

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〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

114