Home » Subject » Graph Theory » Coloring

Linial-Berge path partition duality

Importance: High ✭✭✭
Author(s): Berge, Claude
Linial, Nathan
Subject: Graph Theory
» Coloring
Keywords: coloring
directed path
partition
Recomm. for undergrads: no
Posted by: berger
on: March 27th, 2007
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.

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 $.

add new comment

Berge-Linial conjecture

On September 19th, 2007 Anonymous says:

There is a typo in the formulation :

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

Thanks ! Best, Andras Sebo

reply

Thanks Andras!

On September 19th, 2007 mdevos says:

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

reply

Comment viewing options

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