Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Surjective H-colouring : new hardness results.

Golovach, P.A. and Johnson, M. and Martin, B. and Paulusma, D. and Stewart, A. (2019) 'Surjective H-colouring : new hardness results.', Computability., 8 (1). pp. 27-42.

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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(280Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.3233/COM-180084
Publisher statement:The final publication is available at IOS Press through https://doi.org/10.3233/COM-180084
Date accepted:05 February 2018
Date deposited:05 March 2018
Date of first online publication:15 February 2018
Date first made open access:05 March 2018

Save or Share this output

Export:
Export
Look up in GoogleScholar