![](/files/happy5.png)
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.
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ D $](/files/tex/b8653a25aff72e3dacd3642492c24c2241f0058c.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
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