Skip to main content

Research Repository

Advanced Search

Surjective H-colouring: New hardness results

Golovach, P.A.; Johnson, M.; Martin, B.; Paulusma, D.; Stewart, A.

Surjective H-colouring: New hardness results Thumbnail


P.A. Golovach

A. Stewart


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.


Golovach, P., Johnson, M., Martin, B., Paulusma, D., & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability, 8(1), 27-42.

Journal Article Type Article
Acceptance Date Feb 5, 2018
Online Publication Date Feb 15, 2018
Publication Date 2019
Deposit Date Mar 5, 2018
Publicly Available Date Mar 5, 2018
Journal Computability
Print ISSN 2211-3568
Electronic ISSN 2211-3576
Publisher IOS Press
Peer Reviewed Peer Reviewed
Volume 8
Issue 1
Pages 27-42


You might also like

Downloadable Citations