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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Even pairs
- Perfect graphs