# The perfection and recognition of bull-reducible Berge graphs

Hazel Everett; Celina M. H. de Figueiredo; Sulamita Klein; Bruce Reed^{[1]}

- [1] McGill University, Canada;

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

- 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 - Informatique Théorique et Applications 39.1 (2005): 145-160. <http://eudml.org/doc/245735>.

@article{Everett2005,

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^6)$, is much lower than that announced for perfect graphs.},

affiliation = {McGill University, Canada;},

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

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

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

language = {eng},

number = {1},

pages = {145-160},

publisher = {EDP-Sciences},

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

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

volume = {39},

year = {2005},

}

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 - Informatique Théorique et Applications

PY - 2005

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(n^6)$, 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/245735

ER -

## References

top- [1] C. Berge and V. Chvátal, Topics on Perfect Graphs. North-Holland, Amsterdam, Ann. Discrete Math. 21 (1984). Zbl0546.00006MR778744
- [2] V. Chvátal, Star-cutsets and perfect graphs. J. Combin. Theory Ser. B 39 (1985) 189–199. Zbl0674.05058
- [3] M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour and K. Vuskovic, Cleaning for Bergeness, manuscript (2003).
- [4] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The Strong Perfect Graph Theorem, manuscript (2003). Zbl1112.05042
- [5] M. Chudnovsky and P. Seymour, Recognizing Berge graphs, manuscript (2003). Zbl1089.05027
- [6] V. Chvátal and N. Sbihi, Bull-free Berge graphs are perfect. Graphs Combin. 3 (1987) 127–139. Zbl0633.05056
- [7] 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
- [8] 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
- [9] 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
- [10] R.B. Hayward, Discs in unbreakable graphs. Graphs Combin. 11 (1995) 249–254. Zbl0833.05032
- [11] R.B. Hayward, Bull-free weakly chordal perfectly orderable graphs. Graphs Combin. 17 (2001) 479–500. Zbl1010.05028
- [12] B. Jamison and S. Olariu, ${P}_{4}$-reducible graphs – a class of uniquely tree-representable graphs. Stud. Appl. Math. 81 (1989) 79–87. Zbl0699.05054
- [13] X. Liu, G. Cornuejols and K. Vuskovic, A polynomial algorithm for recognizing perfect graphs, manuscript (2003).
- [14] L. Lovász, Normal hypergraphs and the weak perfect graph conjecture. Discrete Math. 2 (1972) 253–267. Zbl0239.05111
- [15] J.L. Ramirez-Alfonsin and B.A. Reed, Perfect Graphs. Wiley (2001). Zbl0972.00015MR1858793
- [16] 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.