✦ LIBER ✦

New classes of Berge perfect graphs

✍ Scribed by C. De Simone; A. Galluccio

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 823 KB
Volume: 131
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90373-5

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we prove the validity of the Strong Perfect Graph Conjecture for some classes of graphs described by forbidden configurations.

Three different kinds of techniques are used: the first is the well-known star-cutset technique, the second involves a clique-reduction operation, and the third is based on a new equivalence of the Strong Perfect Graph Conjecture.

📜 SIMILAR VOLUMES

Skeletal graphs — a new class of perfect

Skeletal graphs — a new class of perfect graphs

✍ A. Hertz 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 431 KB

Let S be an arbitrary collection of stars in a graph G such that there is no chain of length ~3 joining the centers of (any) two stars in G. We consider the graphs that can be obtained by deleting in a parity graph all the edges of such a set S. These graphs will be called skeletal graphs and we pro

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 new class of perfect Hoàng graphs

✍ Irena Rusu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 314 KB

k-Bounded classes of dominant-independen

k-Bounded classes of dominant-independent perfect graphs

✍ Zverovich, Igor E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 253 KB 👁 2 views

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a f

A class of strongly perfect graphs

✍ M. Preissmann 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 154 KB

On a class of kernel-perfect and kernel-

On a class of kernel-perfect and kernel-perfect-critical graphs

✍ Kiran B. Chilakamarri; Peter Hamburger 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 275 KB

Chilakamarri, K.B. and P. Hamburger, On a class of kernel-perfect and kernel-perfect-critical graphs, Discrete Mathematics 118 (1993) 253-257. In this note we present a construction of a class of graphs in which each of the graphs is either kernel-perfect or kernel-perfect-critical. These graphs or