Strong perfect graph theorem
ID: strong-perfect-graph-theorem
The Strong Perfect Graph Theorem, proved by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas in 2006, establishes an important characterization of perfect graphs. The theorem states that a graph is perfect if and only if it contains no induced subgraph that is an odd cycle of length at least 5 or the complement of such a cycle (i.e., a complete graph minus an odd cycle).
New to topics? Read the docs here!