Mathematics – Combinatorics
Scientific paper
2003-04-28
Proceedings of the ICM, Beijing 2002, vol. 3, 547--560
Mathematics
Combinatorics
Scientific paper
A graph is {\em perfect} if, in all its induced subgraphs, the size of a largest clique is equal to the chromatic number. Examples of perfect graphs include bipartite graphs, line graphs of bipartite graphs and the complements of such graphs. These four classes of perfect graphs will be called {\em basic}. In 1960, Berge formulated two conjectures about perfect graphs, one stronger than the other. The weak perfect graph conjecture, which states that a graph is perfect if and only if its complement is perfect, was proved in 1972 by Lov\'asz. This result is now known as the perfect graph theorem. The strong perfect graph conjecture (SPGC) states that a graph is perfect if and only if it does not contain an odd hole or its complement. The SPGC has attracted a lot of attention. It was proved recently (May 2002) in a remarkable sequence of results by Chudnovsky, Robertson, Seymour and Thomas. The proof is difficult and, as of this writing, they are still checking the details. Here we give a flavor of the proof.
No associations
LandOfFree
The strong perfect graph conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The strong perfect graph conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The strong perfect graph conjecture will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-334004