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.
| Original language | English |
|---|---|
| Pages (from-to) | 71-79 |
| Journal | Journal of Graph Theory |
| Volume | 11 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1987 |
Fingerprint Dive into the research topics of 'Contractilibility and NP-completeness'. Together they form a unique fingerprint.
Cite this
Brouwer, A. E., & Veldman, H. J. (1987). Contractilibility and NP-completeness. Journal of Graph Theory, 11(1), 71-79. https://doi.org/10.1002/jgt.3190110111