# Linial-Berge path partition duality

 Importance: High ✭✭✭
 Author(s): Berge, Claude Linial, Nathan
 Subject: Graph Theory » Coloring
 Keywords: coloring directed path partition
 Posted by: berger on: March 27th, 2007

\begin{conjecture} The minimum $k$-norm of a path partition on a directed graph $D$ is no more than the maximal size of an induced $k$-colorable subgraph. \end{conjecture}

Definitions: Let $D$ be a directed graph. A path partition of $D$ is a set of vertex disjoint paths in it (some might be singletons), covering all vertices. Let $k$ be a positive integer. The $k$ norm of a path partition is the sum of $\min\{|V(P)|,k\}$ for all paths $P$ in it.

This conjecture is known for acyclic graphs and for $k =1,2$.

### Berge-Linial conjecture

There is a typo in the formulation :

Replace "maximum k-norm" by "minimum k-norm".

Thanks ! Best, Andras Sebo

### Thanks Andras!

Thanks much for the correction, I've updated the problem.