𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Normal fraternally orientable graphs satisfy the strong perfect graph conjecture

✍ Scribed by H. Galeana-Sánchez

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
718 KB
Volume
122
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The chromatic number x of a graph G is the minimum number of colors necessary to color the vertices of G such that no two adjacent vertices are colored alike. The clique number 01 of a graph G is the maximum number of vertices in a complete subgraph of G. A graph G is said to be perfect if x(H) =m(H) for every induced subgraph H of G. Berge's strong perfect-graph conjecture states that G is perfect iff G does not contain C,,, 1 and C2"+ r, n > 2 as an induced subgraph.

In this paper we show that this conjecture is true for graphs which accept an orientation such that every complete subgraph has an absorbing vertex and the set of predecessors (resp: successors) of each vertex induces a complete subgraph. Also we obtain an equivalent version of the Strong Perfect Graph Conjecture.

📜 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

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

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

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