2013/01/22 by Nicolas Trotignon, Trotignon, Nicolas · 1 citation
Computer Science · Mathematics · #05C17 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1301.5149
openalex publication_date 2013/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.