A short proof of the Chen-Manalastas theorem (Q1903737): Difference between revisions

The subject theorem by \textit{C. C. Chen} and \textit{P. Manalastas} [Discrete Math. 44, 243-250 (1983; Zbl 0507.05036)] states that a strong digraph \(D\) with stability number at most 2 is spanned by one circuit or by two consistent circuits (their intersection is a path). The author constructs a shorter proof of this result by first refining a result of \textit{T. Gallai} and \textit{A. N. Milgram} [Acta Sci. Math. 21, 181-186 (1960; Zbl 0101.166)] which states that if \(D\) is a digraph with stability number \(\alpha\) and \(\mathcal Q\) is a path partition of \(D\) with head set \(h({\mathcal Q})\) and tail set \(t({\mathcal Q})\) and satisfying \(|{\mathcal Q}|> \alpha\) then there is a path partition \(\mathcal P\) of \(D\) such that \(|{\mathcal P}|= |{\mathcal Q}|- 1\), \(h({\mathcal P})\subseteq h({\mathcal Q})\) and \(t({\mathcal P})\subseteq t({\mathcal Q})\).