Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: LATIN 2022: THEORETICAL INFORMATICS; v. 13568, p. 16-pg., 2022-01-01.

Resumo

Let D be a digraph. A proper 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 some super-orientations of an odd cycle of length at least five and of its complement are not chi-diperfect. In 2022, de Paula Silva, Nunes da Silva and Lee characterized which super-orientations of such graphs are chi-diperfect. In this paper, we show that there are other minimal non-chi-diperfect digraphs with stability number two and three. In particular, the underlying graph of these digraphs with stability number two that we have found are subgraphs of the complement of an odd cycle with at least seven vertices. Motivated by this fact, we introduce a class of graphs, called nice graphs, which consist of all 2-connected graphs in which every odd cycle has length exactly five. We characterize which super-orientations of the complement of a nice graph are chi-diperfect. (AU)

• Processo FAPESP: 20/06116-4 - Dígrafos chi-Diperfeitos
• Beneficiário: Caroline Aparecida de Paula Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• 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