# Linial-Berge path partition duality

**Conjecture**The minimum -norm of a path partition on a directed graph is no more than the maximal size of an induced -colorable subgraph.

**Definitions: ** Let be a directed graph. A path partition of is a set of vertex disjoint paths in it (some might be singletons), covering all vertices. Let be a positive integer. The norm of a path partition is the sum of for all paths in it.

This conjecture is known for acyclic graphs and for .

### Thanks Andras!

On September 19th, 2007 mdevos says:

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

## Berge-Linial conjecture

There is a typo in the formulation :

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

Thanks ! Best, Andras Sebo