Surjective \(H\)-colouring: new hardness results

DOI10.1007/978-3-319-58741-7_26zbMath1489.68192arXiv1701.02188OpenAlexW2963006808MaRDI QIDQ2011662

Anthony Stewart, Barnaby Martin, Daniël Paulusma, Matthew Johnson, Petr A. Golovach

Publication date: 4 August 2017

Full work available at URL: https://arxiv.org/abs/1701.02188

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Algorithms for partition of some class of graphs under compaction and vertex-compaction
• The complexity of surjective homomorphism problems-a survey
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Finding vertex-surjective graph homomorphisms
• A complete complexity classification of the role assignment problem
• On the complexity of H-coloring
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Retractions to Pseudoforests
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Compaction, Retraction, and Constraint Satisfaction
• Computational Complexity of Compaction to Reflexive Cycles
• Bi‐arc graphs and the complexity of list homomorphisms

This page was built for publication: Surjective \(H\)-colouring: new hardness results