Perfect graphs: a survey

Abstract

Perfect graphs were defined by Claude Berge in the 1960s. They are important objects for graph theory, linear programming and combinatorial optimization. Claude Berge made a conjecture about them, that was proved by Chudnovsky, Robertson, Seymour and Thomas in 2002, and is now called the strong perfect graph theorem. This is a survey about perfect graphs, mostly focused on the strong perfect graph theorem.

52 pages; published in Topics in Chromatic Graph Theory, Cambridge University Press, 2015, pp. 137-160

References in corpus (8)

• Detecting induced subgraphs
• Algorithms for perfectly contractile graphs
• Combinatorial optimization with 2-joins
• Vertex elimination orderings for hereditary graph classes
• Decomposing Berge graphs and detecting balanced skew partitions
• Detecting wheels
• On Roussel-Rubio-type lemmas and their consequences
• Odd pairs of cliques

Cited by in corpus (5)

• Vertex elimination orderings for hereditary graph classes
• (Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 1 : Layered wheels
• Clique-Stable Set separation in perfect graphs with no balanced skew-partitions
• A Constructive Formalization of the Weak Perfect Graph Theorem
• A variant of the Lovász-Theta number based on projection matrices