Surjective H-colouring: New hardness results

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

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.

• Journal Article Type: Article
• Acceptance Date: Feb 5, 2018
• Online Publication Date: Feb 15, 2018
• Publication Date: 2019
• Deposit Date: Mar 5, 2018
• Publicly Available Date: Mar 5, 2018
• Journal: Computability
• Print ISSN: 2211-3568
• Electronic ISSN: 2211-3576
• Publisher: IOS Press
• Peer Reviewed: Peer Reviewed
• Volume: 8
• Issue: 1
• Pages: 27-42
• DOI: https://doi.org/10.3233/com-180084
• Public URL: https://durham-repository.worktribe.com/output/1365677