logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

The strong perfect graph theorem

delete2006-07-01
delete777
delete
OA
AI
M
Maria Chudnovsky *
N
Neil Robertson
P
Paul Seymour
R
Robin Thomas
DOI：10.4007/annals.2006.164.51delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
A graph G is perfect if for every induced subgraph H, the chromatic number of H equals the size of the largest complete subgraph of H, and G is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. The strong perfect graph conjecture (Berge, 1961) asserts that a graph is perfect if and only if it is Berge. A stronger conjecture was made recently by Conforti, Cornuejols and Vuskovic-that every Berge graph either falls into one of a few basic classes, or admits one of a few kinds of separation (designed so that a minimum counterexample to Berge's conjecture cannot have either of these properties). In this paper we prove both of these conjectures.
Keywords:
MINIMAL IMPERFECT GRAPHS
DECOMPOSITION
PROPERTY

Journal

Annals of Mathematics cover
Annals of Mathematics
IF:
5.3
Papers:
1.4K
Citations:
1.6W

Organization

No organization information available