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 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2023},
     volume = {43},
     number = {4},
     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
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
%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/

[1] S.D. Andres and W. Hochstättler, Perfect digraphs, J. Graph Theory 79 (2015) 21–29. https://doi.org/10.1002/jgt.21811

[2] S.D. Andres, H. Bergold, W. Hochstättler and J. Wiehe, A semi-strong perfect digraph theorem, AKCE Int. J. Graphs Comb. 17 (2020) 992–994. https://doi.org/10.1016/j.akcej.2019.12.018

[3] J. Bang-Jensen, T. Bellitto, T. Schweser and M. Stiebitz, Hajós and Ore constructions for digraphs, Electron. J. Combin. 27 (2020) #P1.63. https://doi.org/10.37236/8942

[4] E. Boros and V. Gurvich, Perfect graphs are kernel solvable, Discrete Math. 159 (1996) 35–55. https://doi.org/10.1016/0012-365X(95)00096-F

[5] M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour and K. Vušković, Recognizing Berge graphs, Combinatorica 25 (2005) 143–186. https://doi.org/10.1007/s00493-005-0012-8

[6] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect graph theorem, Ann. of Math. (2) 164 (2006) 51–229. https://doi.org/10.4007/annals.2006.164.51

[7] C. Crespelle and C. Paul, Fully dynamic recognition algorithm and certificate for directed cographs, Discrete Appl. Math. 154 (2006) 1722–1741. https://doi.org/10.1016/j.dam.2006.03.005

[8] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second Edition (Ann. Discrete Math. 57, Elsevier, Amsterdam, 2004).

[9] L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972) 253–267. https://doi.org/10.1016/0012-365X(72)90006-4

[10] L. Lovász, A characterization of perfect graphs, J. Combin. Theory Ser. B 13 (1972) 95–98. https://doi.org/10.1016/0095-8956(72)90045-7

[11] V. Neumann-Lara, The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982) 265–270. https://doi.org/10.1016/0095-8956(82)90046-6

[12] B. Reed, A semi-strong perfect graph theorem, J. Combin. Theory Ser. B 43 (1987) 223–240. https://doi.org/10.1016/0095-8956(87)90022-0