✦ LIBER ✦

Even pairs and the strong perfect graph conjecture

✍ Scribed by Stefan Hougardy

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 130 KB
Volume: 154
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00330-l

No coin nor oath required. For personal study only.

✦ Synopsis

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 length at least five. An odd hole is a hole that has an odd number of vertices.

An (odd) anti-hole is the complement of an (odd) hole. Berge's famous Strong Perfect Graph Conjecture may be formulated as follows:

Strong Perfect Graph Conjecture. The only minimal imperfect graphs are the odd holes and the odd anti-holes.

📜 SIMILAR VOLUMES

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

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

Partitionable graphs, circle graphs, and

Partitionable graphs, circle graphs, and the berge strong perfect graph conjecture

✍ Mark A. Buckingham; Martin Charles Golumbic 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 749 KB

A note on the semi-strong perfect graph

A note on the semi-strong perfect graph conjecture

✍ B Reed 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 119 KB

Combinatorial designs related to the str

Combinatorial designs related to the strong perfect graph conjecture

✍ V. Chvátal; R.L. Graham; A.F. Perold; S.H. Whitesides 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 842 KB

Simple solutions of these matrix equations are easy to find; we describe ways of cortstructing rather messy ones. Our investigations are motivated by an intimate relationship between the pairs X, Y and minimal imperfect graphs.

Families of graphs complete for the stro

Families of graphs complete for the strong perfect graph Conjecture

✍ D. G. Corneil 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 381 KB 👁 1 views

The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true