Contractibility and NP-completeness

A.E. Brouwer, H.J. Veldman

Research output: Contribution to journalArticleAcademic

64 Citations (Scopus)
148 Downloads (Pure)


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 languageUndefined
Pages (from-to)71-79
JournalJournal of graph theory
Issue number1
Publication statusPublished - 1987


  • IR-70829

Cite this