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