𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Perfectly contractile diamond-free graphs

✍ Scribed by Rusu, Irena

Book ID
101228221
Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
415 KB
Volume
32
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Coloring Bull-Free Perfectly Contractile
Coloring Bull-Free Perfectly Contractile Graphs
✍ LΓ©vΓͺque, Benjamin; Maffray, FrΓ©dΓ©ric πŸ“‚ Article πŸ“… 2008 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 264 KB
Perfectly contractile graphs
Perfectly contractile graphs
✍ Marc E Bertschi πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 416 KB
Algorithms for Perfectly Contractile Gra
Algorithms for Perfectly Contractile Graphs
✍ Maffray, FrΓ©dΓ©ric; Trotignon, Nicolas πŸ“‚ Article πŸ“… 2005 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 408 KB
On weakly diamond-free Berge graphs
On weakly diamond-free Berge graphs
✍ HacΓ¨ne Ait Haddadene; Sylvain Gravier πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 183 KB

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.

On the connectivity of diamond-free grap
On the connectivity of diamond-free graphs
✍ Peter Dankelmann; Angelika Hellwig; Lutz Volkmann πŸ“‚ Article πŸ“… 2007 πŸ› Elsevier Science 🌐 English βš– 147 KB