Proof of Berge's path partition conjecture for $k\geq\lambda-3$

Dávid Herskovics


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:

AUTHOR = {Herskovics, D{\'a}vid},
TITLE = {Proof of Berge's path partition conjecture for $k\geq\lambda-3$},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2013},
NUMBER = {TR-2013-08}

Last modification: 29.12.2020. Please email your comments to Tamás Király!