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

Abstract

top
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 x a , x b , a b , a d , b c . 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.

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.