Surjective H-Colouring: new hardness results

Golovach, P. A.; Johnson, M.; Martin, M.; 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 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.

Citation

Golovach, P. A., Johnson, M., Martin, M., Paulusma, D., & Stewart, A. (2017, June). Surjective H-Colouring: new hardness results. Presented at Computability in Europe (CiE 2017)., Turku, Finland

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: Computability in Europe (CiE 2017).
• Start Date: Jun 12, 2017
• End Date: Jun 16, 2017
• Acceptance Date: Mar 1, 2017
• Online Publication Date: May 13, 2017
• Publication Date: Jun 1, 2017
• Deposit Date: Mar 10, 2017
• Publicly Available Date: May 12, 2018
• Print ISSN: 0302-9743
• Volume: 10307
• Pages: 270-281
• Series Title: Lecture notes in computer science
• Series ISSN: 0302-9743,1611-3349
• Book Title: Unveiling dynamics an complexity.
• ISBN: 9783319587400
• DOI: https://doi.org/10.1007/978-3-319-58741-7_26
• Public URL: https://durham-repository.worktribe.com/output/1147684
• Related Public URLs: https://arxiv.org/pdf/1701.02188.pdf