Skip to main content

Research Repository

Advanced Search

Surjective H-Colouring over reflexive digraphs

Larose, B.; Martin, B.; Paulusma, D.

Surjective H-Colouring over reflexive digraphs Thumbnail


Authors

B. Larose



Abstract

The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality, the property of a structure that all of its endomorphisms that do not have range of size 1 are automorphisms, as a means to obtain complexity-theoretic classifications of Surjective H-Colouring in the case of reflexive digraphs. Chen (2014) proved, in the setting of constraint satisfaction problems, that Surjective H-Colouring is NP-complete if H has the property that all of its polymorphisms are essentially unary. We give the first concrete application of his result by showing that every endo-trivial reflexive digraph H has this property. We then use the concept of endo-triviality to prove, as our main result, a dichotomy for Surjective H-Colouring when H is a reflexive tournament: if H is transitive, then Surjective H-Colouring is in NL; otherwise, it is NP-complete. By combining this result with some known and new results, we obtain a complexity classification for Surjective H-Colouring when H is a partially reflexive digraph of size at most 3.

Citation

Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over reflexive digraphs. ACM Transactions on Computation Theory, 11(1), Article 3. https://doi.org/10.1145/3282431

Journal Article Type Article
Acceptance Date Sep 8, 2018
Online Publication Date Nov 30, 2018
Publication Date Nov 30, 2018
Deposit Date Sep 10, 2018
Publicly Available Date Sep 11, 2018
Journal ACM Transactions on Computation Theory
Print ISSN 1942-3454
Electronic ISSN 1942-3462
Publisher Association for Computing Machinery (ACM)
Peer Reviewed Peer Reviewed
Volume 11
Issue 1
Article Number 3
DOI https://doi.org/10.1145/3282431
Public URL https://durham-repository.worktribe.com/output/1320642

Files

Accepted Journal Article (911 Kb)
PDF

Copyright Statement
© 2018 Association for Computing Machinery. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM transactions on computation theory, https://doi.org/10.1145/3282431






You might also like



Downloadable Citations