| Full text | |
| Author(s): |
Silva, Caroline Aparecida de Paula
;
Silva, Candida Nunes da
;
Lee, Orlando
Total Authors: 3
|
| Document type: | Journal article |
| Source: | DISCRETE MATHEMATICS; v. 345, n. 9, p. 17-pg., 2022-09-01. |
| Abstract | |
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) | |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 20/06116-4 - chi-Diperfect Digraphs |
| Grantee: | Caroline Aparecida de Paula Silva |
| Support Opportunities: | Scholarships in Brazil - Master |