Contractilibility and NP-completeness

A.E. Brouwer, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

64 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)71-79
JournalJournal of Graph Theory
Issue number1
Publication statusPublished - 1987


Dive into the research topics of 'Contractilibility and NP-completeness'. Together they form a unique fingerprint.

Cite this