On the structure of bull-free perfect graphs |
| |
| Authors: | Celina M. H. de Figueiredo Frédéric Maffray Oscar Porto |
| |
| Affiliation: | (1) Instituto de Matemática, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21944 Rio de Janeiro, RJ, Brasil;(2) LSD2-IMAG, BP 53, 38041 Grenoble Cedex 9, France;(3) Dept. de Engenharia Elétrica, PUC-Rio, Rua Marquês de São Vicente 225, Predio Cardeal Leme, Sala 401, CEP 22453 Rio de Janeiro, RJ, Brasil |
| |
| Abstract: | A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi showed that the Strong Perfect Graph Conjecture holds for bull-free graphs. We show that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. Our proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphsPartially supported by CNPq, grant 30 1160/91.0 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
