Contractibility and NP‐completeness
Andries E. Brouwer, H.J. Veldman · Journal of Graph Theory · 1987
Abstract For a fixed graph H, let H‐CON denote the problem of determining whether a given graph is contractible to H. The complexity of H‐CON is studied for H belonging to certain classes of graphs, together covering all connected graphs of order at most 4. In particular, H‐CON is NP‐complete if H is a connected triangle‐free graph other than a star. For each connected graph H of order at most 4 other than P4 and C4, H‐CON is solvable in polynomial time.