Strong and weak Perfect Digraph Theorems for perfect, $\alpha$-perfect and strictly perfect digraphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 909-930
Voir la notice de l'article provenant de la source Library of Science
Perfect digraphs have been introduced in [S.D. Andres and W. Hochstätt-ler, Perfect digraphs, J. Graph Theory 79 (2015) 21–29] as those digraphs where, for any induced subdigraph, the dichromatic number and the symmetric clique number are equal. Dually, we introduce a directed version of the clique covering number and define α-perfect digraphs as those digraphs where, for any induced subdigraph, the clique covering number and the stability number are equal. It is easy to see that α-perfect digraphs are the complements of perfect digraphs. A digraph is strictly perfect if it is perfect and α-perfect. We generalise the Strong Perfect Graph Theorem and Lovász ([A characterization of perfect graphs, J. Combin. Theory Ser. B 13 (1972) 95–98]) asymmetric version of the Weak Perfect Graph Theorem to the classes of perfect, α-perfect and strictly perfect digraphs. Furthermore, we characterise strictly perfect digraphs by symmetric chords and non-chords in their directed cycles. As an example for a subclass of strictly perfect digraphs, we show that directed cographs are strictly perfect.
Keywords:
perfect digraph, $\alpha$-perfect digraph, strictly perfect digraph, Strong Perfect Graph Theorem, Weak Perfect Graph Theorem, dichromatic number, perfect graph, directed cograph, filled odd hole, filled odd antihole, acyclic set, clique-acyclic clique
@article{DMGT_2023_43_4_a2,
author = {Andres, Stephan Dominique},
title = {Strong and weak {Perfect} {Digraph} {Theorems} for perfect, $\alpha$-perfect and strictly perfect digraphs},
journal = {Discussiones Mathematicae. Graph Theory},
pages = {909--930},
publisher = {mathdoc},
volume = {43},
number = {4},
year = {2023},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a2/}
}
TY - JOUR AU - Andres, Stephan Dominique TI - Strong and weak Perfect Digraph Theorems for perfect, $\alpha$-perfect and strictly perfect digraphs JO - Discussiones Mathematicae. Graph Theory PY - 2023 SP - 909 EP - 930 VL - 43 IS - 4 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a2/ LA - en ID - DMGT_2023_43_4_a2 ER -
%0 Journal Article %A Andres, Stephan Dominique %T Strong and weak Perfect Digraph Theorems for perfect, $\alpha$-perfect and strictly perfect digraphs %J Discussiones Mathematicae. Graph Theory %D 2023 %P 909-930 %V 43 %N 4 %I mathdoc %U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a2/ %G en %F DMGT_2023_43_4_a2
Andres, Stephan Dominique. Strong and weak Perfect Digraph Theorems for perfect, $\alpha$-perfect and strictly perfect digraphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 909-930. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a2/