Perfect Graphs

This web page highlights some of the conjectures and open problems concerning Perfect Graphs.

If you would like to print a hard copy of the whole outline, you can download a dvi, postscript or pdf version.

  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

The individual contributions may have problems because converting complicated TeX into a web page is not an exact science. The dvi, ps, or pdf versions are your best bet.