On the Berge's strong path partition conjecture (Q1210577)

A partition of the vertex set of a graph into paths is called a path partition. By a partial \(k\)-coloring of \(G\), we mean a set of \(k\) mutually disjoint stable sets \(S_ 1,S_ 2,\ldots,S_ k\). A vertex \(x \in S_ i\) is assigned the color \(i\). In a partial \(k\)-coloring a path \(P\) is strongly colored if the number of different colors represented in \(P\) is equal to \(\min \bigl\{ k,| P | \bigr\}\). Let \(k \geq 1\) be an integer. For a path partition \(S=(P_ 1,P_ 2,\ldots,P_ q)\) set \[ B_ k(S)=\sum^{i=q}_{i=1}\min \bigl\{ k,| P_ i | \bigr\}. \] A partition \(S'=(P_ 1,P_ 2,\ldots,P{_ q'})\) is \(k\)-finer then \(S\) if \(B_ k(S')<B_ k(S)\) and \(S'\) is \(k\)-optimal if there is no \(k\)-finer partition than \(S'\). In the present paper the author proved that for every \(k\)-optimal path partition of a digraph in which each component contains at most one cycle, there exists a partial \(k\)-coloring which colors strongly every path of the partition.