A Semi-strong Perfect Digraph Theorem

2019/06/13 by Andres, Stephan Dominique, Bergold, Helena, Hochstättler, Winfried +1
#05C15 #05C17 #05C20 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1906.05650

Abstract

Reed showed that, if two graphs are P₄-isomorphic, then either both are perfect or none of them is. In this note we will derive an analogous result for perfect digraphs.

Related

• The strong perfect graph conjecture
• The strong perfect graph theorem
• Perfect graphs: a survey
• Digraphs modulo primitive positive constructability
• An analogue of Reed's conjecture for digraphs