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

A digraph D verifies the Chvátal-Erdős conditions if α(D)⩽κ(D), where α(D) is the stability number of D and κ(D) 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 α=α(D) vertices {x1,…,xα}, there exists a vertex-partition of D into directed paths {P1,…,Pα} such that Pi begins at xi for all i. The case α(D)=2 of the conjecture is proved.