Article ID Journal Published Year Pages File Type
4650627 Discrete Mathematics 2006 43 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,