Finding vertex-surjective graph homomorphisms

DOI10.1007/s00236-012-0164-0zbMath1253.68149OpenAlexW2974321649MaRDI QIDQ715053

Barnaby Martin, Petr A. Golovach, Bernard Lidický, Daniël Paulusma

Publication date: 15 October 2012

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/10697/1/10697.pdf

zbMATH Keywords

NP-completeguest graphhost graphsurjective homomorphism problem

Mathematics Subject Classification ID

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 (4)

Coloring problems on bipartite graphs of small diameter ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ Surjective \(H\)-colouring: new hardness results ⋮ The Complexity of Counting Surjective Homomorphisms and Compactions

Cites Work

• Unnamed Item
• The complexity of surjective homomorphism problems-a survey
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• A complete complexity classification of the role assignment problem
• On the complexity of H-coloring
• An application of simultaneous diophantine approximation in combinatorial optimization
• Upper bounds to the clique width of graphs
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
• Integer Programming with a Fixed Number of Variables
• Parameterized Algorithms for Boxicity
• Retractions to Pseudoforests
• Algorithms for Partition of Some Class of Graphs under Compaction
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Graph Layout Problems Parameterized by Vertex Cover
• What Makes Equitable Connected Partition Easy
• Compaction, Retraction, and Constraint Satisfaction
• Computational Complexity of Compaction to Reflexive Cycles
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: Finding vertex-surjective graph homomorphisms