Contractibility and NP-completeness


Brouwer, A.E. and Veldman, H.J. (1987) Contractibility and NP-completeness. Journal of Graph Theory, 11 (1). pp. 71-79. ISSN 0364-9024

open access
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.
Item Type:Article
Copyright:© 1987 Wiley InterScience
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page