Classes of perfect graphs |
| |
Affiliation: | Institut für Informatik, Humboldt-Universität zu Berlin, 10099 Berlin, Germany |
| |
Abstract: | The strong perfect graph conjecture, suggested by Claude Berge in 1960, had a major impact on the development of graph theory over the last 40 years. It has led to the definitions and study of many new classes of graphs for which the strong perfect graph conjecture has been verified. Powerful concepts and methods have been developed to prove the strong perfect graph conjecture for these special cases. In this paper we survey 120 of these classes, list their fundamental algorithmic properties and present all known relations between them. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|