Perfectly contractile diamond-free graph
β
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.