Let $D$ be a digraph. A path partition of $D$ is called $k$-optimal if
the sum of the $k$-norms of its paths is minimal. The $k$-norm of a path $P$ is $\min(|V(P)|,k)$.
Berge's path partition conjecture claims that for every $k$-optimal path partition
$\mathcal{P}$ there are $k$ disjoint stable sets orthogonal to $\mathcal{P}$.
For general digraphs the conjecture has been proven for
$k=1,2,\lambda-1,\lambda$, where $\lambda$ is the length of longest path in the digraph.
In this paper we prove the conjecture for $\lambda-2$ and $\lambda -3$.
Previous versions can be found here and here.
Bibtex entry:
@techreport{egres-13-08,
AUTHOR | = | {Herskovics, D{\'a}vid}, |
TITLE | = | {Proof of Berge's path partition conjecture for $k\geq\lambda-3$}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2013}, |
NUMBER | = | {TR-2013-08} |