Issue Theoret. Informatics Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist Page(s) 145 - 160 DOI 10.1051/ita:2005009

Theoret. Informatics Appl. 39, 145-160 (2005)
DOI: 10.1051/ita:2005009

The perfection and recognition of bull-reducible Berge graphs

Hazel Everett¹, Celina M.H. de Figueiredo², Sulamita Klein² and Bruce Reed<sup>3

1</sup>  LORIA, France; Hazel.Everett@loria.fr
²  Universidade Federal do Rio de Janeiro, Brasil; celina@cos.ufrj.br, sula@cos.ufrj.br
³  McGill University, Canada; breed@cs.mcgill.ca

Abstract
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(n⁶), is much lower than that announced for perfect graphs.

Mathematics Subject Classification. 05C17, 05C75, 05C85


© EDP Sciences 2005

What is OpenURL?