# The perfection and recognition of bull-reducible Berge graphs

Hazel Everett; Celina M.H. de Figueiredo; Sulamita Klein; Bruce Reed

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 39, Issue: 1, page 145-160
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topEverett, Hazel, et al. "The perfection and recognition of bull-reducible Berge graphs." RAIRO - Theoretical Informatics and Applications 39.1 (2010): 145-160. <http://eudml.org/doc/92752>.

@article{Everett2010,

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.
},

author = {Everett, Hazel, de Figueiredo, Celina M.H., Klein, Sulamita, Reed, Bruce},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {perfect graph; strong perfect graph conjecture; bull; efficient algorithm},

language = {eng},

month = {3},

number = {1},

pages = {145-160},

publisher = {EDP Sciences},

title = {The perfection and recognition of bull-reducible Berge graphs},

url = {http://eudml.org/doc/92752},

volume = {39},

year = {2010},

}

TY - JOUR

AU - Everett, Hazel

AU - de Figueiredo, Celina M.H.

AU - Klein, Sulamita

AU - Reed, Bruce

TI - The perfection and recognition of bull-reducible Berge graphs

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 39

IS - 1

SP - 145

EP - 160

AB -
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.

LA - eng

KW - perfect graph; strong perfect graph conjecture; bull; efficient algorithm

UR - http://eudml.org/doc/92752

ER -

## References

top- C. Berge and V. Chvátal, Topics on Perfect Graphs. North-Holland, Amsterdam, Ann. Discrete Math.21 (1984). Zbl0546.00006
- V. Chvátal, Star-cutsets and perfect graphs. J. Combin. Theory Ser. B39 (1985) 189–199. Zbl0674.05058
- M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour and K. Vuskovic, Cleaning for Bergeness, manuscript (2003).
- M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The Strong Perfect Graph Theorem, manuscript (2003). Zbl1112.05042
- M. Chudnovsky and P. Seymour, Recognizing Berge graphs, manuscript (2003). Zbl1089.05027
- V. Chvátal and N. Sbihi, Bull-free Berge graphs are perfect. Graphs Combin.3 (1987) 127–139. Zbl0633.05056
- C.M.H. de Figueiredo, F. Maffray and O. Porto, On the structure of bull-free perfect graphs. Graphs Combin.13 (1997) 31–55. Zbl0869.05028
- C.M.H. de Figueiredo, F. Maffray and O. Porto, On the structure of bull-free perfect graphs, 2: The weakly chordal case. Graphs Combin.17 (2001) 435–456. Zbl1008.05074
- M. Grötschel, L. Lovász and A. Schrijver, Polynomial algorithms for perfect graphs, in Topics on Perfect Graphs, edited by C. Berge and V. Chvátal. North-Holland, Amsterdam, Ann. Discrete Math.21 (1984) 325–356. Zbl0554.05041
- R.B. Hayward, Discs in unbreakable graphs. Graphs Combin.11 (1995) 249–254. Zbl0833.05032
- R.B. Hayward, Bull-free weakly chordal perfectly orderable graphs. Graphs Combin.17 (2001) 479–500. Zbl1010.05028
- B. Jamison and S. Olariu, P4-reducible graphs – a class of uniquely tree-representable graphs. Stud. Appl. Math.81 (1989) 79–87. Zbl0699.05054
- X. Liu, G. Cornuejols and K. Vuskovic, A polynomial algorithm for recognizing perfect graphs, manuscript (2003).
- L. Lovász, Normal hypergraphs and the weak perfect graph conjecture. Discrete Math.2 (1972) 253–267. Zbl0239.05111
- J.L. Ramirez-Alfonsin and B.A. Reed, Perfect Graphs. Wiley (2001).
- B. Reed and N. Sbihi, Recognizing bull-free perfect graphs. Graphs Combin.11 (1995) 171–178. Zbl0832.05039

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.