Proof of Berge’s path partition conjecture for k≥λ−3k≥λ−3

Let DD be a digraph. A path partition   of DD is called kk-optimal if the sum of the kk-norms of its paths is minimal. The k-norm   of a path PP is min(|V(P)|,k)min(|V(P)|,k). Berge’s path partition conjecture claims that for every kk-optimal path partition PP there are kk disjoint stable sets orthogonal to PP. For general digraphs the conjecture has been proven for k=1,2,λ−1,λk=1,2,λ−1,λ, where λλ is the length of a longest path in the digraph. In this paper we prove the conjecture for λ−2λ−2 and λ−3λ−3.