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 if it has no induced subgraph isomorphic to an odd cycle of length at least five, or the complement of such a cycle. A related open question is whether perfectness can be tested in polynomial time. The PI and his colleagues are pursuing a strategy for proving the SPGC. They have formulated several conjectures about graph decomposition that together with earlier conjectures and results imply the SPGC, and are working toward establishing the validity of those conjectures.
This work falls within the area of graph theory, and is closely related to theoretical computer science and mathematical programming (operations research). A graph is an abstract mathematical notion used to model networks, such as telephone networks, transportation networks or the Internet. Within graph theory the class of perfect graphs is important for several reasons. For instance, many problems of interest in practice that are intractable in general can be solved efficiently when restricted to the class of perfect graphs. Also, the question of when a certain class of linear programs always have an integer solution can be answered in terms of the perfectness of an associated graph. Thus the Strong Perfect Graph Conjecture is believed to be an important open problem, and its resolution is likely to have implications in the design of efficient algorithms of interest to theoretical computer scientists and operations researchers.
