We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Matthew Johnson

Golovach, P. A., Johnson, M., Martin, M., Paulusma, D. & Stewart, A. (2017), Surjective H-Colouring: new hardness results, in Kari J., Manea F. & Petre I. eds, Lecture Notes in Computer Science 10307: Computability in Europe (CiE 2017). Turku, Finland, Springer, Cham, 270-281.

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