Vertex partition problems in digraphs - Sambinelli, M.; Lintzmayer, C. N.; da Silva, C. N.; Lee, O. (Anais do Encontro de Teoria da Computação (ETC); 2018: Anais do III Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2018.3174, 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.