TR-2013-08

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

Dávid Herskovics



Abstract

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}
}


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