×

A semi-strong perfect digraph theorem. (English) Zbl 1468.05089

Summary: B. Reed [J. Comb. Theory, Ser. B 43, 223–240 (1987; Zbl 0647.05052)] showed that, if two graphs are \(P_4 \)-isomorphic, then either both are perfect or none of them is. In this note, we will derive an analogous result for perfect digraphs.

MSC:

05C17 Perfect graphs
05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 0647.05052
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Andres, S. D.; Hochstättler, W., Perfect digraphs, J. Graph Theory, 79, 1, 21-29 (2015) · Zbl 1312.05059
[2] Bang-Jensen, J.; Gutin, G., Digraphs. Theory, Algorithms and Applications (2009), London: Springer-Verlag London Ltd, London · Zbl 1170.05002
[3] Chvátal, V., A semi-strong perfect graph conjecture, Ann. Discrete Math., 21, 279-280 (1984) · Zbl 0557.05043
[4] Corneil, D. G.; Lerchs, H.; Burlingham, L. S., Complement reducible graphs, Discrete Appl. Math., 3, 3, 163-174 (1981) · Zbl 0463.05057
[5] Crespelle, C.; Paul, C., Fully dynamic recognition algorithm and certificate for directed cographs, Discrete Appl. Math., 154, 12, 1722-1741 (2006) · Zbl 1110.68096
[6] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, 57 (2004), Amsterdam: Elsevier, Amsterdam · Zbl 1050.05002
[7] Neumann-Lara, V., The dichromatic number of a digraph, J. Combin. Theory Ser. B, 33, 3, 265-270 (1982) · Zbl 0506.05031
[8] Reed, B., A semi-strong perfect graph theorem, J. Combin. Theory Ser. B, 43, 2, 223-240 (1987) · Zbl 0647.05052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.