Finding vertex-surjective graph homomorphisms

DOI10.1007/S00236-012-0164-0zbMATH Open1253.68149OpenAlexW2974321649MaRDI QIDQ715053FDOQ715053

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

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

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)

Cites Work

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

Cited In (5)

• On retracts, absolute retracts, and foldings in cographs
• Coloring problems on bipartite graphs of small diameter
• The Complexity of Counting Surjective Homomorphisms and Compactions
• Surjective \(H\)-colouring: new hardness results
• Computing vertex-surjective homomorphisms to partially reflexive trees

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)