Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00324584
Contributor : Stéphane Bessy <>
Submitted on : Thursday, September 25, 2008 - 2:38:35 PM
Last modification on : Thursday, July 19, 2018 - 11:54:04 AM

Identifiers

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⟩

Share

Metrics

Record views

373