Obstructions for χ-diperfectness

Autor(es)

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

• Tipo de documento: Artigo Científico
• Fonte: XII LATIN-AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, LAGOS 2023; v. 224, p. 8-pg., 2023-01-01.

Resumo

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 is a path P containing exactly one vertex of each color class of S and this property holds for every induced subdigraph of D. The ultimate goal in this research area is to obtain a characterization of chi-diperfect digraphs in terms of forbidden induced subdigraphs, but this may be a very difficult problem and not likely to be solved in a near future. Berge showed the first examples of obstructions for chi-diperfect digraphs (i.e. minimal non-chi-diperfect digraphs) by presenting orientations of odd cycles and complements of odd cycles that are not chi-diperfect. In 2022, de Paula Silva, Nunes da Silva and Lee showed characterizations of non-chi-diperfect super-orientations of odd cycles and their complements. Moreover, they showed that these structures are not the only obstructions for chi-diperfect digraphs, by presenting new obstructions with stability number two and three. In this paper, we present new obstructions for chi-diperfect digraphs with arbitrary stability number and arbitrary chromatic number. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0) (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: 22/03735-0 - Digrafos alpha-Diperfeitos e chi-Diperfeitos
• Beneficiário: Caroline Aparecida de Paula Silva
• Modalidade de apoio: Bolsas no Brasil - Doutorado