A semi-strong perfect digraph theorem

DOI10.1016/J.AKCEJ.2019.12.018MaRDI QIDQ4956212zbMATH OpenOpenAlexFDO

Authors Stephan Dominique Andres, Helena Bergold, Winfried. Hochstättler, Johanna Wiehe

Publication date 1 September 2021

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1906.05650

zbMATH Keywords

dichromatic numberperfect digraphperfect graph

Mathematics Subject Classification ID

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

Abstract: Reed 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.

Recommendations

• A semi-strong perfect graph theorem
• The P₄-structure of perfect graphs
• scientific article; zbMATH DE number 3887731
• Perfect graphs with unique \(P_ 4\)-structure
• Recognizing the \(P_4\)-structure of bipartite graphs

Cites work

• A semi-strong perfect graph theorem
• Algorithmic graph theory and perfect graphs
• Complement reducible graphs
• Digraphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• scientific article; zbMATH DE number 3887731 (Why is no real title available?)
• Perfect digraphs
• The dichromatic number of a digraph

Cited in

(4)

• A semi-strong perfect graph theorem
• Perfect graphs with unique \(P_ 4\)-structure
• scientific article; zbMATH DE number 3887731 (Why is no real title available?)
• Strong and weak perfect digraph theorems for perfect, -perfect and strictly perfect digraphs

This page was built for publication: A semi-strong perfect digraph theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4956212)