@inproceedings { ,
title = {Surjective H-Colouring: new hardness results},
abstract = {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.},
conference = {Computability in Europe (CiE 2017).},
doi = {10.1007/978-3-319-58741-7\_26},
isbn = {9783319587400},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {270-281},
publicationstatus = {Published},
url = {https://durham-repository.worktribe.com/output/1147684},
volume = {10307},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2017},
author = {Golovach, P. A. and Johnson, M. and Martin, M. and Paulusma, D. and Stewart, A.}
editor = {Kari, J. and Manea, F. and Petre, I.}
}