Theory Seminar

Abstract

A graph is perfect if all of its induced subgraphs have the property that their chromatic number equals the size of their largest clique. This class of graphs was introduced by Berge in 1961, when he also conjectured that a graph is perfect if and only if neither the graph nor its complement contains and odd hole. This conjecture remains open to this day and is known as the Strong Perfect Graph Conjecture. An important aspect of perfect graphs is that certain optimization problems, such as maximum weighted stable set, minimum weighted covering of vertices by cliques, maximum weighted clique and minimum weighted covering of vertices by stable sets, that are NP-complete in general, can be solved in polynomial time for perfect graphs. What remains open is whether we can recognize perfect graphs in polynomial time.

In this talk we present how the above two problems can be approached using the decomposition method, and survey some of the recent results in this area.