Paths partition with prescribed beginnings in digraphs: A Chvátal–Erdős condition approach

Stéphane Bessy 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A digraph D verifies the Chvátal–Erdős conditions if , where is the stability number of D and is its vertex-connectivity. Related to the Gallai–Milgram Theorem (see Gallai and Milgram [Verallgemeinerung eines Graphentheorischen Satzes von Redei, Acta Sci. Math. 21 (1960) 181–186]), we raise in this context the following conjecture. For every set of vertices , there exists a vertex-partition of D into directed paths such that begins at for all i. The case of the conjecture is proved.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2008, 308 (18), pp.4108-4115. 〈10.1016/j.disc.2007.07.113〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324584
Contributeur : Stéphane Bessy <>
Soumis le : jeudi 25 septembre 2008 - 14:38:35
Dernière modification le : jeudi 19 juillet 2018 - 11:54:04

Lien texte intégral

Identifiants

Collections

Citation

Stéphane Bessy. Paths partition with prescribed beginnings in digraphs: A Chvátal–Erdős condition approach. Discrete Mathematics, Elsevier, 2008, 308 (18), pp.4108-4115. 〈10.1016/j.disc.2007.07.113〉. 〈lirmm-00324584〉

Partager

Métriques

Consultations de la notice

127