α-diperfect digraphs - Sambinelli, M.; 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.3173, 2018)
Let D be a digraph. A path partition P of D is a collection of paths such that {V(P) : P ∈ 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 ∈ 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 x 1 x 2 · · · x 2k+1 x 1 , where k ≥ 2, (ii) the longest path in C has length 2, and (iii) each of the vertices x 1 , x 2 , x 3 , x 4 , x 6 , x 8 , . . . , x 2k 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.