Progress on perfect graphs |
| |
| Authors: | Maria Chudnovsky Neil Robertson P. D. Seymour Robin Thomas |
| |
| Affiliation: | (1) Department of Mathematics, Princeton University, Princeton, NJ 08544, USA, US;(2) Department of Mathematics, Ohio State University, 231 W. 18th Ave., Columbus, Ohio 43210, USA, US;(3) Department of Mathematics, Princeton University, Princeton, NJ 08544, USA, US;(4) School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, USA, US |
| |
| Abstract: | A graph is perfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The class of perfect graphs is important for several reasons. For instance, many problems of interest in practice but intractable in general can be solved efficiently when restricted to the class of perfect graphs. Also, the question of when a certain class of linear programs always have an integer solution can be answered in terms of perfection of an associated graph. In the first part of the paper we survey the main aspects of perfect graphs and their relevance. In the second part we outline our recent proof of the Strong Perfect Graph Conjecture of Berge from 1961, the following: a graph is perfect if and only if it has no induced subgraph isomorphic to an odd cycle of length at least five, or the complement of such an odd cycle. Received: December 19, 2002 / Accepted: April 29, 2003 Published online: May 28, 2003 Key words. Berge graph – perfect graph – skew partition Mathematics Subject Classification (1991): 05C17 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
