Forbidden induced subgraph characterizations of subclasses and variations of perfect graphs: A survey |
| |
| Affiliation: | 1. Instituto de Cálculo and Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina;2. Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile;3. CONICET, Argentina;1. Institute for Software Technology, University of Technology, Graz, Austria;2. Instituto de Matemáticas, Universidad Nacional Autónoma de México, D.F. México, México |
| |
| Abstract: | A graph is perfect if the chromatic number is equal to the clique number for every induced subgraph of the graph. Perfect graphs were defined by Berge in the sixties. In this survey we present known results about partial characterizations by forbidden induced subgraphs of different graph classes related to perfect graphs. We analyze a variation of perfect graphs, clique-perfect graphs, and two subclasses of perfect graphs, coordinated graphs and balanced graphs. |
| |
| Keywords: | balanced graphs clique graphs clique-perfect graphs coordinated graphs K-perfect graphs perfect graphs |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
