Even pairs in Berge graphs

Research output: Contribution to journalArticle

9 Scopus citations

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 languageEnglish (US)
Pages (from-to)370-377
Number of pages8
JournalJournal of Combinatorial Theory. Series B
Volume99
Issue number2
DOIs
StatePublished - Mar 1 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Even pairs
  • Perfect graphs

Fingerprint Dive into the research topics of 'Even pairs in Berge graphs'. Together they form a unique fingerprint.

Cite this