Vertex partition problems in digraphs ⇤

  • M. Sambinelli
  • C. N. Lintzmayer
  • C. N. da Silva
  • O. Lee


Let D be a digraph and k be a positive integer. Linial (1981) conjectured that the k-norm of a k-minimum path partition of a digraph D is at most max{PC2 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.

SAMBINELLI, M.; LINTZMAYER, C. N.; DA SILVA, C. N.; LEE, O.. Vertex partition problems in digraphs ⇤. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: