Article in volume
Authors:
Title:
Strong and weak Perfect Digraph Theorems for perfect, $\alpha$-perfect and strictly perfect digraphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 909-930
Received: 2020-09-07 , Revised: 2021-05-12 , Accepted: 2021-05-12 , Available online: 2021-06-18 , https://doi.org/10.7151/dmgt.2413
Abstract:
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 $\alpha$-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 $\alpha$-perfect digraphs are the
complements of perfect digraphs. A digraph is strictly perfect if it
is perfect and $\alpha$-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,
$\alpha$-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
References:
- S.D. Andres and W. Hochstättler, Perfect digraphs, J. Graph Theory 79 (2015) 21–29.
https://doi.org/10.1002/jgt.21811 - 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 - 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 - 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 - 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 - 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 - 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 - M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second Edition (Ann. Discrete Math. 57, Elsevier, Amsterdam, 2004).
- 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 - 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 - 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 - 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
Close