Publication details for Professor Matthew JohnsonGolovach, P.A., Johnson, M., Martin, B., Paulusma, D. & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability 8(1): 27-42.
- Publication type: Journal Article
- ISSN/ISBN: 2211-3568 (print), 2211-3576 (electronic)
- DOI: 10.3233/COM-180084
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring problem is to decide if a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the Surjective H-Colouring problem, which imposes the homomorphism to be vertex-surjective. We build upon previous results and show that this problem is NP-complete for every connected graph H that has exactly two vertices with a self-loop as long as these two vertices are not adjacent. As a result, we can classify the computational complexity of Surjective H-Colouring for every graph H on at most four vertices.