χ-Diperfect Digraphs

• Caroline A. de Paula Silva UNICAMP
• Orlando Lee UNICAMP
• Cândida N. da Silva UFSCar

DOI: https://doi.org/10.5753/ctd.2023.229897

Resumo

In 1982, Berge defined the class of χ-diperfect digraphs. A digraph D is χ-diperfect if for every induced subdigraph H of D and every minimum coloring S of H there exists a path P of H with exactly one vertex of each color class of S. Berge also showed examples of non-χ-diperfect orientations of odd cycles and their complements. The ultimate goal in this research area is to obtain a characterization of χ-diperfect digraphs in terms of forbidden induced subdigraphs. In this work, we give steps towards this goal by presenting characterizations of orientations of odd cycles and their complements that are χ-diperfect. We also show that certain classes of digraphs are χ-diperfect. Moreover, we present minimal non-χ-diperfect digraphs that were unknown.

Referências

Bang-Jensen, J. (1990). Locally semicomplete digraphs: a generalization of tournaments. Journal of Graph Theory, 14(3):371–390.

Bang-Jensen, J. (1995). Digraphs with the path-merging property. Journal of Graph Theory, 20(2):255–265.

Berge, C. (1961). Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind. Wissenschaftliche Zeitschrift.

Berge, C. (1982). Diperfect graphs. Combinatorica, 2(3):213–222.

Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Springer.

Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. (2006). The Strong Perfect Graph Theorem. Annals of Mathematics, 164:51–229.

Chudnovsky, M., Robertson, N., Seymour, P. D., and Thomas, R. (2003). Progress on perfect graphs. Mathematical Programming, 97:405–422.

de Paula Silva, C. A. (2022). χ-Diperfect Digraphs. Master’s thesis, State University of Campinas UNICAMP.

de Paula Silva, C. A., da Silva, C. N., and Lee, O. A family of counterexamples for a conjecture of Berge on α-diperfect digraphs. Submitted. https://arxiv.org/abs/2207.08007.

de Paula Silva, C. A., da Silva, C. N., and Lee, O. (2022a). χ-Diperfect digraphs. Discrete Mathematics, 345(9):112941.

de Paula Silva, C. A., da Silva, C. N., and Lee, O. (2022b). On χ-Diperfect Digraphs with Stability Number Two. In Castañeda, A. and Rodríguez-Henríquez, F., editors, LATIN 2022: Theoretical Informatics, pages 460–475, Cham. Springer International Publishing.

Freitas, L. I. B. and Lee, O. (2021). Some results on structure of all arc-locally (out) in-semicomplete digraphs. https://arxiv.org/abs/2104.11019.

Gallai, T. (1968). On directed paths and circuits. Theory of graphs, pages 115–118.

Grötschel, M., Lovász, L., and Schrijver, A. (1984). Polynomial algorithms for perfect graphs. In North-Holland mathematics studies, volume 88, pages 325–356. Elsevier.

Lovász, L. (1972). Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics, 2(3):253–267.

Rédei, L. (1934). Ein kombinatorischer satz. Acta Litt. Szeged, 7(39-43):97.

Roy, B. (1967). Nombre chromatique et plus longs chemins d’un graphe. ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 1(5):129–132.

Wang, S. and Wang, R. (2009). The structure of strong arc-locally in-semicomplete digraphs. Discrete Mathematics, 309(23-24):6555–6562.