Geodesic
The perfection and recognition of bull-reducible Berge graphs
Everett, Hazel ; de Figueiredo, Celina M. H. ; Klein, Sulamita ; Reed, Bruce1 idref
1McGill University, Canada;
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 145-160
Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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},
     year = {2005},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {1},
     doi = {10.1051/ita:2005009},
     mrnumber = {2132584},
     zbl = {1063.05055},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :