Characterization and Recognition of Perfect Graphs

一个图是完美的，如果对每一个导出子图，色数等于一个完全子图的最大尺寸。Berge在1960年提出的强完美图猜想（SPGC）指出，一个图是完美的当且仅当它没有导出子图同构于一个长度至少为5的奇圈，或这个奇圈的补图。一个相关的开放问题是完美性是否可以在多项式时间内测试。 PI和他的同事们正在寻求一种证明SPGC的策略。他们已经制定了几个关于图分解的理论，这些理论与早期的理论和结果一起暗示了SPGC，并且正在努力建立这些理论的有效性。这项工作福尔斯图论领域，与理论计算机科学和数学规划（运筹学）密切相关。图是一个抽象的数学概念，用于对网络进行建模，例如电话网络，交通网络或互联网。在图论中，完美图类是重要的，有几个原因。例如，许多在实践中感兴趣的问题，通常是棘手的，可以有效地解决时，限制到完美图类。此外，当某类线性规划总是有一个整数解的问题可以回答在相关的图的完美性。因此，强完美图猜想被认为是一个重要的开放问题，它的解决可能会对理论计算机科学家和操作研究人员感兴趣的高效算法的设计产生影响。

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 decompositionthat 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 resolutionis likely to have implications in the design of efficient algorithms of interest to theoretical computer scientists and operations researchers.