Abstract
Our proof (with Robertson and Thomas) of the strong perfect graph conjecture ran to 179 pages of dense matter; and the most impenetrable part was the final 55 pages, on what we called "wheel systems." In this paper we give a replacement for those 55 pages, much easier and shorter, using "even pairs." This is based on an approach of Maffray and Trotignon.
Original language | English (US) |
---|---|
Pages (from-to) | 370-377 |
Number of pages | 8 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 99 |
Issue number | 2 |
DOIs | |
State | Published - Mar 2009 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- Even pairs
- Perfect graphs