The complexity of locally injective homomorphisms

DOI10.1016/j.disc.2010.03.034zbMath1219.05062OpenAlexW2077159664WikidataQ114190776 ScholiaQ114190776MaRDI QIDQ709315

Jacobus Swarts, Gary MacGillivray

Publication date: 18 October 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2010.03.034

zbMATH Keywords

complexityNP-completenesspolynomial algorithmlocally injective homomorphismdigraph homomorphism

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Unnamed Item ⋮ Obstructions to locally injective oriented improper colourings ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs
• On the complexity of H-coloring
• On the injective chromatic number of graphs
• On the computational complexity of partial covers of theta graphs
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• Partial covers of graphs
• Pattern Matching in Protein-Protein Interaction Graphs
• Mathematical Foundations of Computer Science 2005
• Digraphs
• Oriented graph coloring

This page was built for publication: The complexity of locally injective homomorphisms