The perfection and recognition of bull-reducible Berge graphs
Everett, Hazel ; de Figueiredo, Celina M. H. ; Klein, Sulamita ; Reed, Bruce
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005), p. 145-160 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2005-01-01
DOI : https://doi.org/10.1051/ita:2005009
Classification:  05C17,  05C75,  05C85 
@article{ITA_2005__39_1_145_0,
     author = {Everett, Hazel and de Figueiredo, Celina M. H. and Klein, Sulamita and Reed, Bruce},
     title = {The perfection and recognition of bull-reducible Berge graphs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {39},
     year = {2005},
     pages = {145-160},
     doi = {10.1051/ita:2005009},
     mrnumber = {2132584},
     zbl = {1063.05055},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2005__39_1_145_0}
}

Everett, Hazel; de Figueiredo, Celina M. H.; Klein, Sulamita; Reed, Bruce. The perfection and recognition of bull-reducible Berge graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) pp. 145-160. doi : 10.1051/ita:2005009. http://gdmltest.u-ga.fr/item/ITA_2005__39_1_145_0/

[1] C. Berge and V. Chvátal, Topics on Perfect Graphs. North-Holland, Amsterdam, Ann. Discrete Math. 21 (1984). | MR 778744 | Zbl 0546.00006

[2] V. Chvátal, Star-cutsets and perfect graphs. J. Combin. Theory Ser. B 39 (1985) 189-199. | Zbl 0674.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).

[5] M. Chudnovsky and P. Seymour, Recognizing Berge graphs, manuscript (2003).

[6] V. Chvátal and N. Sbihi, Bull-free Berge graphs are perfect. Graphs Combin. 3 (1987) 127-139. | Zbl 0633.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. | Zbl 0869.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. | Zbl 1008.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. | Zbl 0554.05041

[10] R.B. Hayward, Discs in unbreakable graphs. Graphs Combin. 11 (1995) 249-254. | Zbl 0833.05032

[11] R.B. Hayward, Bull-free weakly chordal perfectly orderable graphs. Graphs Combin. 17 (2001) 479-500. | Zbl 1010.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. | Zbl 0699.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. | Zbl 0239.05111

[15] J.L. Ramirez-Alfonsin and B.A. Reed, Perfect Graphs. Wiley (2001). | MR 1858793 | Zbl 0972.00015

[16] B. Reed and N. Sbihi, Recognizing bull-free perfect graphs. Graphs Combin. 11 (1995) 171-178. | Zbl 0832.05039