The perfection and recognition of bull-reducible Berge graphs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 145-160.

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.

DOI : 10.1051/ita:2005009
Classification : 05C17, 05C75, 05C85
Everett, Hazel  ; de Figueiredo, Celina M. H.  ; Klein, Sulamita  ; Reed, Bruce 1

1 McGill University, Canada; 
@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},
     pages = {145--160},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {1},
     year = {2005},
     doi = {10.1051/ita:2005009},
     mrnumber = {2132584},
     zbl = {1063.05055},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita:2005009/}
}
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
SP  - 145
EP  - 160
VL  - 39
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2005009/
DO  - 10.1051/ita:2005009
LA  - en
ID  - ITA_2005__39_1_145_0
ER  - 
%0 Journal Article
%A Everett, Hazel
%A de Figueiredo, Celina M. H.
%A Klein, Sulamita
%A Reed, Bruce
%T The perfection and recognition of bull-reducible Berge graphs
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2005
%P 145-160
%V 39
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2005009/
%R 10.1051/ita:2005009
%G en
%F 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) no. 1, pp. 145-160. doi : 10.1051/ita:2005009. http://archive.numdam.org/articles/10.1051/ita:2005009/

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

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

[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

[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

[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

[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

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

[11] R.B. Hayward, Bull-free weakly chordal perfectly orderable graphs. Graphs Combin. 17 (2001) 479-500. | Zbl

[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

[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

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

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

Cité par Sources :