Perfection and Beyond
summary
Describes the proof that Strong Perfect Graph Theorem holds via a triple of results: classify Berge graphs as five basic classes (bipartite, complements, line-graphs of bipartite and their complements, double-split) or admit decompositions (skew partitions, two-joins; later even and dominant pairs shorten the proof). Proof is long (≈150 pages, later cut by ~30%). Gives a recognition n^9 algorithm, notes open combinatorial coloring of perfect graphs, and surveys chi-bounded and Erdős–Hajnal–type conjectures for forests and tournaments.
AI-written summary · about
chapters (14)
- 0:00Intro
- 2:30Inequality
- 5:12Perfect graphs
- 9:15Odd graphs
- 12:03Weak perfect graphs
- 15:35Proof of Strong Perfect
- 17:09Triple Theorems
- 20:59Compositions
- 24:01Proof
- 35:34Chi boundedness
- 36:47Induced subgraphs
- 40:32Shadow conjecture
- 43:56Open cases
- 46:33Compatability graphs
related talks
18mOn the Verification of a Subgraph Construction Algorithm
01h 00mThe Classification Program for Counting Problems I
23mA New Connection Between Node and Edge Depth Robust Graphs
55mLower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic
01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting Complexity
01h 05mCertifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
01h 00mAverage-case Complexity for Polynomials, and All That
30mThe Hitting Proof System