Bull-free Berge graphs are perfect |
| |
| Authors: | Vašek Chvátal Najiba Sbihi |
| |
| Affiliation: | (1) Department of Computer Science, Rutgers University, 08903 New Brunswick, NJ, USA;(2) Centre National de Coordination et de Planification de la Recherche Scientifique et Technique, B.P. 1346, Rabat, R.P., Morocco |
| |
| Abstract: | Abull is the (self-complementary) graph with verticesa, b, c, d, e and edgesab, ac, bc, bd, ce; a graphG is calledBerge if neitherG not its complement contains a chordless cycle whose length is odd and at least five. We prove that bull-free Berge graphs are perfect; a part of our argument relies on a new property of minimal imperfect graphs.This work was done while both authors were at the School of Computer Science, McGill University; support by NSERC is gratefully acknowledged. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
