Finding vertex-surjective graph homomorphisms
type: Item
instance of: scholarly article
title: Finding vertex-surjective graph homomorphisms
zbMATH Open document ID: 1253.68149
author: Petr A. Golovach
author: Bernard Lidický
author: Barnaby Martin
author: Daniël Paulusma
published in: Acta Informatica
publication date: 2012-10-15T00:00:00Z
full work available at URL: 10697.pdf
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 6093699
zbMATH Keywords: surjective homomorphism problem
zbMATH Keywords: guest graph
zbMATH Keywords: host graph
zbMATH Keywords: NP-complete
MaRDI profile type: Publication
OpenAlex ID: W2974321649
cites work: Parameterized Algorithms for Boxicity
cites work: The complexity of surjective homomorphism problems-a survey
cites work: Improved Parameterized Upper Bounds for Vertex Cover
cites work: Upper bounds to the clique width of graphs
cites work: What Makes Equitable Connected Partition Easy
cites work: Retractions to Pseudoforests
cites work: Graph Layout Problems Parameterized by Vertex Cover
cites work: Locally constrained graph homomorphisms -- structure, complexity, and applications
cites work: Parameterized complexity of coloring problems: treewidth versus vertex cover
cites work: A complete complexity classification of the role assignment problem
cites work: An application of simultaneous diophantine approximation in combinatorial optimization
cites work: Q4198056
cites work: Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
cites work: The complexity of homomorphism and constraint satisfaction problems seen from the other side
cites work: On the complexity of H-coloring
cites work: Integer Programming with a Fixed Number of Variables
cites work: Computational Complexity of Compaction to Reflexive Cycles
cites work: Compaction, Retraction, and Constraint Satisfaction
cites work: A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
cites work: Algorithms for Partition of Some Class of Graphs under Compaction
DOI: 10.1007/S00236-012-0164-0
description: scientific article; zbMATH DE number 6093699