Skip to main content

Research Repository

Advanced Search

Surjective H-Colouring: new hardness results

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

Surjective H-Colouring: new hardness results Thumbnail


P. A. Golovach

M. Martin

A. Stewart


J. Kari

F. Manea

I. Petre


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.


Golovach, P. A., Johnson, M., Martin, M., Paulusma, D., & Stewart, A. (2017). Surjective H-Colouring: new hardness results. In J. Kari, F. Manea, & I. Petre (Eds.), Unveiling dynamics an complexity (270-281).

Conference Name Computability in Europe (CiE 2017).
Conference Location Turku, Finland
Start Date Jun 12, 2017
End Date Jun 16, 2017
Acceptance Date Mar 1, 2017
Online Publication Date May 13, 2017
Publication Date Jun 1, 2017
Deposit Date Mar 10, 2017
Publicly Available Date May 12, 2018
Volume 10307
Pages 270-281
Series Title Lecture notes in computer science
Series ISSN 0302-9743,1611-3349
Book Title Unveiling dynamics an complexity.
ISBN 9783319587400
Public URL
Related Public URLs


You might also like

Downloadable Citations