Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
From MaRDI portal
Publication:3522938
DOI10.1007/11917496_2zbMath1167.68406OpenAlexW1482949867MaRDI QIDQ3522938
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (13)
List covering of regular multigraphs ⋮ Graph covers: where topology meets computer science, and simple means difficult ⋮ List covering of regular multigraphs with semi-edges ⋮ Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs ⋮ Locally constrained graph homomorphisms -- structure, complexity, and applications ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism ⋮ Complexity of Locally Injective Homomorphism to the Theta Graphs ⋮ Locally Injective Homomorphism to the Simple Weight Graphs ⋮ Unnamed Item ⋮ The complexity of locally injective homomorphisms ⋮ Obstructions to locally injective oriented improper colourings ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
This page was built for publication: Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
