Digrafos chi-diperfeitos

Author(s)

Caroline Aparecida de Paula Silva

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2022-04-08

Examining board members

Orlando Lee; Maycon Sambinelli; Cláudio Leonardo Lucchesi

• Advisor: Orlando Lee; Candida Nunes da Silva

Abstract

Let D be a digraph. A coloring S and a path P of D are orthogonal if P contains exactly one vertex of each color class in S. In 1982, Berge defined the class of chi-diperfect digraphs. A digraph D is chi-diperfect if for every minimum coloring S of D, there exists a path P orthogonal to S and this property holds for every induced subdigraph of D. Berge showed that every symmetric digraph is chi-diperfect, as well as every digraph whose underlying graph is perfect. However, he also showed that not every super-orientation of an odd cycle or the complement of an odd cycle is chi-diperfect. The ultimate goal of this research area would be to obtain a characterization of chi-diperfect digraphs in terms of forbidden subdigraphs, but this may be a very difficult problem and not likely to be solved in a near future. Non-chi-diperfect super-orientations of odd cycles and their complements may play an important role in the characterization of chi-diperfect digraphs, similarly to the role they play in the characterization of perfect graphs. In this dissertation, we present a characterization of super-orientations of odd cycles and a characterization of super-orientations of complements of odd cycles that are chi-diperfect. We also show that locally in-semicomplete digraphs and locally arc in-semicomplete digraphs are chi-diperfect. Furthermore, we present some examples of minimal non-chi-diperfect digraphs which were not known yet (AU)

• FAPESP's process: 20/06116-4 - chi-Diperfect Digraphs
• Grantee: Caroline Aparecida de Paula Silva
• Support Opportunities: Scholarships in Brazil - Master