Perfectly contractile diamond-free graphs
Irena Rusu · Journal of Graph Theory · 1999
Everett et al. [Everett et al., Discr Math, 1997] conjectured that 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. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 359–389, 1999