On the complexity of recognizing decomposable perfect graphs
Résumé
Chvátal, Lenhart and Sbihi identified six classes of graphs that are perfect if and only if two subgraphs induced by a specific colouring of the vertices are perfect. It is well-known that one of these classes is recognizable in polynomial time. We prove that the recognition of the five other classes is NP-complete.