On the strong path partition conjecture of Berge (Q686176)

Let \(G\) be a directed graph in which not two cycles have a common vertex and whose longest path contains at least \(k\) \((\geq 1)\) vertices. Consider any partition of the vertices of \(G\) into paths \(P_ 1,\ldots,P_ s\) such that \(\sum^ s_ 1\min \bigl\{ | P_ i |,k \bigr\}\) is as small as possible. The author shows that there exists a set of \(k\) mutually disjoint stable sets of \(G\) such that the number of different sets represented by the vertices on each path \(P_ i\) is \(\min \bigl\{ | P_ i |,k \bigr\}\) for \(1 \leq i \leq s\).