𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the strong perfect graph conjecture

✍ Scribed by V Chvátal

Publisher
Elsevier Science
Year
1976
Tongue
English
Weight
144 KB
Volume
20
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the strong perfect graph conjecture
On the strong perfect graph conjecture
✍ Stephan Olariu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

A graph G is perfect if for every induced subgraph H of G the chromatic number x(H) equals the largest number w ( H ) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement C contains an odd cho

Even pairs and the strong perfect graph
Even pairs and the strong perfect graph conjecture
✍ Stefan Hougardy 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 130 KB

We will characterize all graphs that have the property that the graph and its complement are minimal even pair free. This characterization allows a new formulation of the Strong Perfect Graph Conjecture. The reader is assumed to be familiar with perfect graphs (see e.g. [2]). A hole is a cycle of l

Split-Neighborhood Graphs and the Strong
Split-Neighborhood Graphs and the Strong Perfect Graph Conjecture
✍ F. Maffray; M. Preissmann 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 649 KB

We introduce the class of graphs such that every induced subgraph possesses a vertex whose neighbourhood can be split into a clique and a stable set. We prove that this class satisfies Berge's strong perfect graph conjecture. This class contains several well-known classes of (perfect) graphs and is