EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO-Theor. Inf. 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 Everett1, Celina M.H. de Figueiredo2, Sulamita Klein2 and Bruce Reed3

1  LORIA, France; Hazel.Everett@loria.fr
2  Universidade Federal do Rio de Janeiro, Brasil; celina@cos.ufrj.br, sula@cos.ufrj.br
3  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(n6), is much lower than that announced for perfect graphs.


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


© EDP Sciences 2005


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.