Finding vertex-surjective graph homomorphisms

DOI10.1007/S00236-012-0164-0MaRDI QIDQ715053zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Bernard Lidický, Barnaby Martin, 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

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Finding vertex-surjective graph homomorphisms
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Surjective \(H\)-colouring: new hardness results
• Surjective \(H\)-colouring: new hardness results

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• A complete complexity classification of the role assignment problem
• Algorithms for partition of some class of graphs under compaction
• An application of simultaneous diophantine approximation in combinatorial optimization
• Compaction, Retraction, and Constraint Satisfaction
• Computational Complexity of Compaction to Reflexive Cycles
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Graph Layout Problems Parameterized by Vertex Cover
• Improved Parameterized Upper Bounds for Vertex Cover
• Integer Programming with a Fixed Number of Variables
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• On the complexity of H-coloring
• Parameterized algorithms for boxicity
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Retractions to Pseudoforests
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of surjective homomorphism problems-a survey
• Upper bounds to the clique width of graphs
• What makes equitable connected partition easy

Cited in

(8)

• Coloring problems on bipartite graphs of small diameter
• Finding vertex-surjective graph homomorphisms
• Computing vertex-surjective homomorphisms to partially reflexive trees
• The complexity of surjective homomorphism problems-a survey
• On retracts, absolute retracts, and foldings in cographs
• Computing vertex-surjective homomorphisms to partially reflexive trees
• The complexity of counting surjective homomorphisms and compactions
• Surjective \(H\)-colouring: new hardness results

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q715053)