? -Diperfect digraphs

Autor(es)

Silva, Caroline Aparecida de Paula ; Silva, Candida Nunes da ; Lee, Orlando

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE MATHEMATICS; v. 345, n. 9, p. 17-pg., 2022-09-01.

Resumo

Let D be a digraph. A coloring C and a path P of D are orthogonal if P contains exactly one vertex of each color class in C. In 1982, Berge defined the class of chi-diperfect digraphs. A digraph D is chi-diperfect if for every minimum coloring C of D, there exists a path P orthogonal to C 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 complement of an odd cycle is chi-diperfect. 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 paper, 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. Moreover, we show that certain classes of digraphs that are free of such non-chi-diperfect structures are chi-diperfect.(c) 2022 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 20/06116-4 - Dígrafos chi-Diperfeitos
• Beneficiário: Caroline Aparecida de Paula Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado