tailieunhanh - Đề tài "The strong perfect graph theorem "

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, Cornu´jols and Vuˇkovi´ — that every Berge graph either falls into e s c one of a few basic classes, or. | Annals of Mathematics The strong perfect graph theorem By Maria Chudnovsky Neil Robertson Paul Seymour and Robin Thomasn Annals of Mathematics 164 2006 51 229 The strong perfect graph theorem By Maria Chudnovsky Neil Robertson Paul Seymour and Robin Thomas Abstract 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. 1. Introduction We begin with definitions of some of our terms which may be nonstandard. All graphs in this paper are finite and simple. The complement G of a graph G has the same vertex set as G and distinct vertices u v are adjacent in G just when they are not adjacent in G. A hole of G is an induced subgraph of G which is a cycle of length at least 4. An antihole of G is an induced subgraph of G whose complement is a hole in G. A graph G is Berge if every hole and antihole of G has even length. A clique in G is a subset X of V G such that every two members of X are adjacent. A graph G is perfect if for every induced subgraph H of G Supported by ONR grant N00014-01-1-0608 NSF grant DMS-0071096 and AIM. Supported by ONR grants N00014-97-1-0512 and N00014-01-1-0608 and NSF grant DMS-0070912. Supported by ONR grant N00014-01-1-0608 NSF grants DMS-9970514 and DMS-0200595 and AIM. 52 M. CHUDNOVSKY N. ROBERTSON P. SEYMOUR AND R. THOMAS the chromatic number of H equals the size of the largest clique of H. The study of perfect .