Vertex partition problems in digraphs
Maycon Sambinelli, Carla Négri Lintzmayer, C. N. da Silva, O. Lee · 2018
Let D be a digraph and k be a positive integer. Linial (1981) conjec tured that the k-norm of a k-minimum path partition of a digraph D is at most max{ΣC∈C |C| : C is a partial k-coloring of D}. Berge (1982) conjectured that every k-minimum path partition contains a partial k-coloring orthogonal to it. It is well known that Berge’s Conjecture implies Linial’s Conjecture. In this work, we verify Berge’s Conjecture, and consequently Linial’s Conjecture, for locally in-semicomplete digraphs and k-minimum path partitions containing only two paths. Moreover, we verify a conjecture related to Berge’s and Linial’s Conjectures for locally in-semicomplete digraphs.