Home » Subject » Graph Theory » Coloring
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 $.

2 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options