The Perfect Graph Conjecture
October 30 to November 3, 2002
at the
American Institute of Mathematics,
Palo Alto, California
organized by
Paul Seymour and Robin Thomas
Original Announcement
This workshop will be devoted to the recent
solution of the Strong Perfect Graph Conjecture and its implications to
further research in and applications of perfect graphs.
We are bringing together researchers in mathematics, computer science
and operations research with common interest in the interdisciplinary area
of perfect graphs. We hope especially to present new techniques, facilitate
exchange of ideas, share available techniques and outline a strategy for
future reseach.
The main questions to be addressed concern

recognition of perfect graphs

possible structural characterization of perfect graphs

coloring and optimization on perfect graphs without using the ellipsoid
method
Material from the workshop
A list of participants.
The workshop schedule.
A report on the workshop activities.
Workshop Materials:
 Recognition of Perfect Graphs
 Polynomial Recognition Algorithm Found
 Interaction Between SkewPartitions and 2joins
 The PerfectGraph Robust Algorithm Problem
 NP Characterization of Perfect Graphs
 Recognition Algorithm Given the List of Maximal Cliques
 Berge Graphs with Polybounded Number of Max Cliques
 TDI Matrices
 Fixed Parameter Algorithms
 Clique Joins
 Polynomial Size Decomposition Tree
 Structural Characterization of Perfect Graphs
 Coloring Perfect Graphs
 Uniquely colorable perfect graphs
 Optimization on Perfect Graphs
 New Optimization Problems on Perfect Graphs
 A Possible New Problem
 SkewPartitions
 Extending a Skew Partition
 Graphs Without SkewPartitions
 Graphs Without Star Cutsets
 Finding SkewPartitions in Berge Graphs
 Interaction Between Different SkewPartitions in a Graph
 Skew Partitions of Balanced Size
 Recognizing Balanced SkewPartitions
 EvenPair SkewPartition
 Even Pairs in Berge Graphs
 Coloring Berge Graphs Using Even Pairs
 Recognizing Even Pairs
 QuasiParity and Strict QuasiParity Graphs
 Forbidden Subgraphs for The Class of Strict QuasiParity Graphs
 Recognition of QuasiParity and Strict QuasiParity Graphs
 Perfectly Contractile Graphs
 Perfectly Contractile Graphs and the Decomposition Method
 Possible Structure Theorem for Berge Graphs
 Odd holes and odd walks
 Forbidding Holes and Antiholes
 2divisible Graphs
 Clique Coloring of Perfect Graphs
 Recognition of OddHoleFree Graphs
 EvenHoleFree Graphs
 Evenholefree circulants,
 betaperfect graphs
 Partitionable Graphs
 Perfect, Partitionable, and KernelSolvable Graphs
 Partitionable graphs and odd holes
 A Property of Partitionable Graphs
 Small Transversals in Partitionable Graphs
 The Imperfection Ratio
 Integer Programming
 Partitionable Graphs as Cutting Planes for Packing Problems?
 Feasibility/Membership Problem For the Theta Body
 Balanced Graphs
 Balanced circulants
 P4structure and Its Relatives