Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy

DOI10.1007/11917496_2MaRDI QIDQ3522938zbMATH OpenOpenAlexFDO

Authors Jiří Fiala, Jan Kratochvíl

Publication date 4 September 2008

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11917496_2

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The dichotomy of list homomorphisms for digraphs
• Exact algorithm for graph homomorphism and locally injective graph homomorphism
• Locally injective homomorphism to the simple weight graphs
• List homomorphisms to reflexive graphs
• List-homomorphism problems on graphs and arc consistency
• List homomorphisms to separable signed graphs
• The complexity of locally injective homomorphisms
• Complexity of locally injective homomorphism to the Theta graphs
• The complexity of the list homomorphism problem for graphs
• The complexity of the list homomorphism problem for graphs

Cited in

(16)

• List covering of regular multigraphs
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• Exact algorithm for graph homomorphism and locally injective graph homomorphism
• Obstructions to locally injective oriented improper colourings
• Obstructions to injective oriented colourings
• Complexity of locally injective homomorphism to the Theta graphs
• Locally injective homomorphism to the simple weight graphs
• Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
• Complexity of locally-injective homomorphisms to tournaments
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Graph covers: where topology meets computer science, and simple means difficult
• List covering of regular multigraphs with semi-edges
• Computational complexity of covering multigraphs with semi-edges: small cases
• The complexity of locally injective homomorphisms
• Computational complexity of covering regular trees

This page was built for publication: Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy

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