The perfection and recognition of bull-reducible Berge graphs
2 Universidade Federal do Rio de Janeiro, Brasil; email@example.com, firstname.lastname@example.org
3 McGill University, Canada; email@example.com
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 x, a, b, c, d and five edges xa, xb, ab, ad, bc. 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 directly from the Strong Perfect Graph Theorem, our proof leads to a recognition algorithm for this new class of perfect graphs whose complexity, O(n6), is much lower than that announced for perfect graphs.
Mathematics Subject Classification: 05C17 / 05C75 / 05C85
© EDP Sciences, 2005