Atlas home || Conferences | Abstracts | about Atlas

25th Australasian Conference on Combinatorial Mathematics and Combinatorial Computing
December 4-8, 2000
University of Canterbury
Christchurch, New Zealand

Organizers
Charles Semple, Mike Steel

View Abstracts
Conference Homepage

Can the strong perfect graph conjecture be proved?
by
Robin Thomas
Georgia Institute of Technology
Coauthors: Neil Robertson, Paul Seymour

A graph is perfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The Strong Perfect Graph Conjecture (SPGC) of Berge from 1960 asserts that a graph is perfect if and only it has no induced subgraph isomorphic to an odd cycle of length at least five (an `odd hole'), or the complement of such a cycle (an `odd antihole').

We will discuss examples of perfect graphs and their importance. Then we will describe an approach to the SPGC based on decomposing graphs with no odd holes or odd antiholes, and will present a decomposition result for graphs with no odd holes and no K4 subgraph.

Date received: November 10, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafn-50.