1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Strong and Weak Perfect Digraph Theorems for Perfect, α-Perfect and Strictly Perfect Digraphs

Published Online: 08 Jul 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 07 Sep 2020
Accepted: 12 May 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

Perfect digraphs have been introduced in [S.D. Andres and W. Hochstättler, 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

MSC 2010

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

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

[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/894210.37236/8942Search in Google Scholar

[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-F10.1016/0012-365X(95)00096-FSearch in Google Scholar

[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-810.1007/s00493-005-0012-8Search in Google Scholar

[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.5110.4007/annals.2006.164.51Search in Google Scholar

[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.00510.1016/j.dam.2006.03.005Search in Google Scholar

[8] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Second Edition (Ann. Discrete Math. 57, Elsevier, Amsterdam, 2004).10.1016/S0167-5060(04)80051-7Search in Google Scholar

[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-410.1016/0012-365X(72)90006-4Search in Google Scholar

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

[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-610.1016/0095-8956(82)90046-6Search in Google Scholar

[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-010.1016/0095-8956(87)90022-0Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo