Contractilibility and NP-completeness

A.E. Brouwer; H.J. Veldman

doi:10.1002/jgt.3190110111

Contractilibility and NP-completeness

A.E. Brouwer, H.J. Veldman

Discrete Algebra and Geometry

Research output: Contribution to journal › Article › Academic › peer-review

54 Citations (Scopus)

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	https://doi.org/10.1002/jgt.3190110111
Publication status	Published - 1987

Access to Document

10.1002/jgt.3190110111

Fingerprint Dive into the research topics of 'Contractilibility and NP-completeness'. Together they form a unique fingerprint.

Cite this

@article{136402cb00a542faae9a171c1aef2572,

title = "Contractilibility and NP-completeness",

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.",

author = "A.E. Brouwer and H.J. Veldman",

year = "1987",

doi = "10.1002/jgt.3190110111",

language = "English",

volume = "11",

pages = "71--79",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Contractilibility and NP-completeness

AU - Brouwer, A.E.

AU - Veldman, H.J.

PY - 1987

Y1 - 1987

N2 - 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.

AB - 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.

U2 - 10.1002/jgt.3190110111

DO - 10.1002/jgt.3190110111

M3 - Article

VL - 11

SP - 71

EP - 79

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 1

ER -