Strong perfect graph theorem
Perfect iff no odd hole (odd cycle ≥ 5 without chord) or odd antihole. Proven 2006 by Chudnovsky et al.
Advertisement
Polynomial coloring
Coloring, max clique, min clique cover, max indep set all polynomial on perfect graphs. Grötschel-Lovász-Schrijver via LP.
Advertisement
Examples
Bipartite: trivially perfect. Chordal. Interval. Comparability graphs. Permutation graphs.
Recognition
O(V⁹) — polynomial but massive constant. Chudnovsky-Cornuéjols-Liu-Seymour-Vušković.