Surjective H-colouring: New hardness results.

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 if a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the SurjectiveH-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 SurjectiveH-Colouring for every graph H on at most four vertices. [ABSTRACT FROM AUTHOR]