We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Surjective H-Colouring : new hardness results.

Golovach, P. A. and Johnson, M. and Martin, M. and Paulusma, D. and Stewart, A. (2017) 'Surjective H-Colouring : new hardness results.', in Unveiling dynamics an complexity. Cham: Springer, pp. 270-281. Lecture notes in computer science., 10307


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 whether or not a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the Surjective HH -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 HH -Colouring for every graph H on at most four vertices.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:01 March 2017
Date deposited:13 March 2017
Date of first online publication:13 May 2017
Date first made open access:12 May 2018

Save or Share this output

Look up in GoogleScholar