✦ LIBER ✦

Skeletal graphs — a new class of perfect graphs

✍ Scribed by A. Hertz

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 431 KB
Volume: 78
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90184-2

No coin nor oath required. For personal study only.

✦ Synopsis

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 prove that they are strict quasi-parity graphs and hence perfect graphs.

📜 SIMILAR VOLUMES

A new class of perfect Hoàng graphs

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

New classes of Berge perfect graphs

✍ C. De Simone; A. Galluccio 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 823 KB

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 thi

A class of strongly perfect graphs

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

A generalization of perfect graphs?i-per

A generalization of perfect graphs?i-perfect graphs

✍ Cai, Leizhen; Corneil, Derek 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 1003 KB

Let i be a positive integer. We generalize the chromatic number x ( G ) of G and the clique number w(G) of G as follows: The i-chromatic number of G , denoted by x Z ( G ) , is the least number k for which G has a vertex partition V,, V,, . . . , Vk: such that the clique number of the subgraph induc

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

The n-ordered graphs: A new graph class

✍ Anthony Bonato; Jeannette Janssen; Changping Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

## Abstract For a positive integer __n__, we introduce the new graph class of __n__‐ordered graphs, which generalize partial __n__‐trees. Several characterizations are given for the finite __n__‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs __R__