The perfection and recognition of bull-reducible Berge graphs
Hazel Everett, Celina M.H. de Figueiredo, Sulamita Klein, Bruce Reed (2010)
RAIRO - Theoretical Informatics and Applications
Similarity:
The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices and five edges . A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows...