✦ LIBER ✦

A characterization of perfect graphs

✍ Scribed by L Lovász

Publisher: Elsevier Science
Year: 1972
Tongue: English
Weight: 139 KB
Volume: 13
Category: Article
ISSN: 0095-8956
DOI: 10.1016/0095-8956(72)90045-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A characterization of domination perfect

A characterization of domination perfect graphs

✍ I. E. Zverovich; V. E. Zverovich 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB

Let u(G) and i(G) be the domination number and independent domination number of a graph G. respectively. Sumner and Moore [8] define a graph G to be domination perfect if y( H) = i( H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization o

A Characterization of b-Perfect Graphs

✍ Chính T. Hoàng; Frédéric Maffray; Meriem Mechebbek 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 316 KB

## Abstract A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph __G__ is the largest integer __k__ such that __G__ admits a b‐coloring with __k__ colors. A graph is b

A characterization of normal fraternally

A characterization of normal fraternally orientable perfect graphs

✍ H. Galeana-Sánchez 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 255 KB

While the famous Berge's Strong Perfect Graph Conjecture remains a major unsolved problem in Graph Theory, the following alternative characterization of perfect graphs was conjectured in 1982 by C. Berge and P. Duchet: A graph G is perfect if and only if any normal orientation of G is kernel-perfect

A note on the characterization of domina

A note on the characterization of domination perfect graphs

✍ Jason Fulman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB

## Abstract A graph __G__ is domination perfect if for each induced subgraph __H__ of __G__, γ(__H__) = __i__(__H__), where γ and __i__ are a graph's domination number and independent domination number, respectively. Zverovich and Zverovich [3] offered a finite forbidden induced characterization of

A semi-induced subgraph characterization

A semi-induced subgraph characterization of upper domination perfect graphs

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

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl

Generating and characterizing the perfec

Generating and characterizing the perfect elimination orderings of a chordal graph

✍ L.S. Chandran; L. Ibarra; F. Ruskey; J. Sawada 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 402 KB

We develop a constant time transposition "oracle" for the set of perfect elimination orderings of chordal graphs. Using this oracle, we can generate a Gray code of all perfect elimination orderings in constant amortized time using known results about antimatroids. Using clique trees, we show how the