𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On weakly diamond-free Berge graphs

✍ Scribed by Hacène Ait Haddadene; Sylvain Gravier

Book ID
103062474
Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
183 KB
Volume
159
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we present a new class of graphs named weakly diamond-Jree (WDF) graphs and we prove for it the strong perfect graph conjecture, by exhibiting a polynomial sequential (,)-coloring algorithm. This class contains chordal graphs and perfect line-graphs.

📜 SIMILAR VOLUMES

Perfectly contractile diamond-free graph
Perfectly contractile diamond-free graphs
✍ Rusu, Irena 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 415 KB

a graph with no odd hole and no stretcher is perfectly contractile, i.e., it can be reduced to a clique by successively contracting even pairs. We show that this conjecture is true for diamond-free graphs, and propose a polynomial algorithm to perform the successive contractions.