Geodesic
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/