Surjective H-colouring: New hardness results

Article type: Research Article

Authors: Golovach, Petr A.^{a; *} | Johnson, Matthew^b | Martin, Barnaby^c | Paulusma, Daniël^d | Stewart, Anthony^e

Affiliations: [a] Department of Informatics, University of Bergen, Norway. petr.golovach@ii.uib.no | [b] Department of Computer Science, Durham University, U.K.. matthew.johnson@durham.ac.uk | [c] Department of Computer Science, Durham University, U.K.. barnaby.d.martin@durham.ac.uk | [d] Department of Computer Science, Durham University, U.K.. daniel.paulusma@durham.ac.uk | [e] Department of Computer Science, Durham University, U.K.. a.g.stewart@durham.ac.uk

Correspondence: [*] Corresponding author. petr.golovach@ii.uib.no.

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

Keywords: Graph homomorphism, vertex surjectivity, computational complexity

DOI: 10.3233/COM-180084

Journal: Computability, vol. 8, no. 1, pp. 27-42, 2019