χ-Diperfect Digraphs - Silva, Caroline A. de Paula; Lee, Orlando; Silva, Cândida N. da (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2023: Anais do XXXVI Concurso de Teses e Dissertações, 2023)
In 1982, Berge defined the class of χ-diperfect digraphs. A digraph D is χ-diperfect if for every induced subdigraph H of D and every minimum coloring S of H there exists a path P of H with exactly one vertex of each color class of S. Berge also showed examples of non-χ-diperfect orientations of odd cycles and their complements. The ultimate goal in this research area is to obtain a characterization of χ-diperfect digraphs in terms of forbidden induced subdigraphs. In this work, we give steps towards this goal by presenting characterizations of orientations of odd cycles and their complements that are χ-diperfect. We also show that certain classes of digraphs are χ-diperfect. Moreover, we present minimal non-χ-diperfect digraphs that were unknown.