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 and five edges . 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, , is much lower than that announced for perfect graphs.
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ita:2005009/
[1] and, Topics on Perfect Graphs. North-Holland, Amsterdam, Ann. Discrete Math. 21 (1984). | MR | Zbl
[2] , Star-cutsets and perfect graphs. J. Combin. Theory Ser. B 39 (1985) 189-199. | Zbl
[3] ,,, and, Cleaning for Bergeness, manuscript (2003).
[4] ,, and, The Strong Perfect Graph Theorem, manuscript (2003).
[5] and, Recognizing Berge graphs, manuscript (2003).
[6] and, Bull-free Berge graphs are perfect. Graphs Combin. 3 (1987) 127-139. | Zbl
[7] , and, On the structure of bull-free perfect graphs. Graphs Combin. 13 (1997) 31-55. | Zbl
[8] , and, On the structure of bull-free perfect graphs, 2: The weakly chordal case. Graphs Combin. 17 (2001) 435-456. | Zbl
[9] , and, 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] , Discs in unbreakable graphs. Graphs Combin. 11 (1995) 249-254. | Zbl
[11] , Bull-free weakly chordal perfectly orderable graphs. Graphs Combin. 17 (2001) 479-500. | Zbl
[12] and, -reducible graphs - a class of uniquely tree-representable graphs. Stud. Appl. Math. 81 (1989) 79-87. | Zbl
[13] , and, A polynomial algorithm for recognizing perfect graphs, manuscript (2003).
[14] , Normal hypergraphs and the weak perfect graph conjecture. Discrete Math. 2 (1972) 253-267. | Zbl
[15] and, Perfect Graphs. Wiley (2001). | MR | Zbl
[16] and, Recognizing bull-free perfect graphs. Graphs Combin. 11 (1995) 171-178. | Zbl
Cité par Sources :
