Linial-Berge path partition duality

Importance: High ✭✭✭
Subject: Graph Theory
» Coloring
Recomm. for undergrads: no
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.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.