### 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