Abstract : Berge's well known SPGC (Strong Perfect Graph Conjecture) 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. We prove that every bull-reducible Berge graph is perfect and we exhibit a polynomial-time recognition algorithm for bull-reducible Berge graphs.
