P.A. Golovach
Surjective H-colouring: New hardness results
Golovach, P.A.; Johnson, M.; Martin, B.; Paulusma, D.; Stewart, A.
Authors
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
A. Stewart
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.
Citation
Golovach, P., Johnson, M., Martin, B., Paulusma, D., & Stewart, A. (2019). Surjective H-colouring: New hardness results. Computability, 8(1), 27-42. https://doi.org/10.3233/com-180084
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 |
Files
Accepted Journal Article
(286 Kb)
PDF
Copyright Statement
The final publication is available at IOS Press through https://doi.org/10.3233/COM-180084
You might also like
Independent transversals versus transversals
(2019)
Conference Proceeding
Connected vertex cover for (sP1+P5)-free graphs
(2019)
Journal Article
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Finding a small number of colourful components
(2019)
Conference Proceeding
Clique-width for hereditary graph classes
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search