Diperfect Digraphs

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

Resumo


Let D be a digraph. A path partition P of D is a collection of paths such that {V (P ) : P 2 P } is a partition of V (D). We say D is ↵ -diperfect if for every maximum stable set S of D there exists a path partition P of D such that |S \ V (P )| = 1 for all P 2 P and this property holds for every induced subdigraph of D. A digraph C is an anti-directed odd cycle if (i) the underlying graph of C is a cycle x1x2 · · · x2k+1x1, where k 2, (ii) the longest path in C has length 2, and (iii) each of the vertices x1, x2, x3, x4, x6, x8, . . . , x2k is either a source or a sink. Berge (1982) conjectured that a digraph D is ↵ -diperfect if, and only if, D contains no induced anti-directed odd cycle. In this work, we verify this conjecture for digraphs whose underlying graph is series-parallel and for in-semicomplete digraphs.

Publicado
26/07/2018
SAMBINELLI, M.; DA SILVA, C. N.; LEE, O.. Diperfect 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: https://doi.org/10.5753/etc.2018.3173.