Abstract :
Gallai and Milgram (1960) proved that a digraph with stability number α is spanned by α disjoint directed paths. Chen and Manalastas Jr (1983) proved that a strong digraph with stability number at most two is spanned by at most two consistent directed circuits. We slightly simplify the proof of the Gallai-Milgram theorem, while at the same time refining its statement, and use this sharpened version to obtain a relatively short proof of the Chen-Manalastas theorem. We also give a counterexample to a generalization of the Gallai-Milgram theorem conjectured by Hartman (1988).
