Contractilibility and NP-completeness

A.E. Brouwer, H.J. Veldman

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

64 Citaten (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.
Originele taal-2Engels
Pagina's (van-tot)71-79
TijdschriftJournal of Graph Theory
Nummer van het tijdschrift1
StatusGepubliceerd - 1987


Duik in de onderzoeksthema's van 'Contractilibility and NP-completeness'. Samen vormen ze een unieke vingerafdruk.

Citeer dit