The Perfect Graph Conjecture

October 30 to November 3, 2002

at the

American Institute of Mathematics, San Jose, 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

Material from the workshop

A list of participants.

The workshop schedule.

A report on the workshop activities.

Workshop Materials:

  1. Recognition of Perfect Graphs
    1. Polynomial Recognition Algorithm Found
    2. Interaction Between Skew-Partitions and 2-joins
    3. The Perfect-Graph Robust Algorithm Problem
    4. NP Characterization of Perfect Graphs
    5. Recognition Algorithm Given the List of Maximal Cliques
      1. Berge Graphs with Poly-bounded Number of Max Cliques
    6. TDI Matrices
    7. Fixed Parameter Algorithms
    8. Clique Joins
    9. Polynomial Size Decomposition Tree
  2. Structural Characterization of Perfect Graphs
  3. Coloring Perfect Graphs
    1. Uniquely colorable perfect graphs
  4. Optimization on Perfect Graphs
    1. New Optimization Problems on Perfect Graphs
      1. A Possible New Problem
  5. Skew-Partitions
    1. Extending a Skew -Partition
    2. Graphs Without Skew-Partitions
    3. Graphs Without Star Cutsets
    4. Finding Skew-Partitions in Berge Graphs
    5. Interaction Between Different Skew-Partitions in a Graph
    6. Skew -Partitions of Balanced Size
    7. Recognizing Balanced Skew-Partitions
    8. Even-Pair Skew-Partition
  6. Even Pairs in Berge Graphs
    1. Coloring Berge Graphs Using Even Pairs
    2. Recognizing Even Pairs
    3. Quasi-Parity and Strict Quasi-Parity Graphs
      1. Forbidden Subgraphs for The Class of Strict Quasi-Parity Graphs
      2. Recognition of Quasi-Parity and Strict Quasi-Parity Graphs
    4. Perfectly Contractile Graphs
      1. Perfectly Contractile Graphs and the Decomposition Method
    5. Possible Structure Theorem for Berge Graphs
    6. Odd holes and odd walks
  7. Forbidding Holes and Antiholes
    1. 2-divisible Graphs
    2. Clique Coloring of Perfect Graphs
    3. Recognition of Odd-Hole-Free Graphs
    4. Even-Hole-Free Graphs
    5. Even-hole-free circulants,
    6. beta-perfect graphs
  8. Partitionable Graphs
    1. Perfect, Partitionable, and Kernel-Solvable Graphs
    2. Partitionable graphs and odd holes
    3. A Property of Partitionable Graphs
    4. Small Transversals in Partitionable Graphs
  9. The Imperfection Ratio
  10. Integer Programming
    1. Partitionable Graphs as Cutting Planes for Packing Problems?
    2. Feasibility/Membership Problem For the Theta Body
  11. Balanced Graphs
    1. Balanced circulants
  12. P4-structure and Its Relatives