Complexity of Locally Injective Homomorphism to the Theta Graphs

DOI10.1007/978-3-642-19222-7_33zbMath1326.68163OpenAlexW1609919256MaRDI QIDQ3000520

Bernard Lidický, Marek Tesař

Publication date: 19 May 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_33

zbMATH Keywords

computational complexitylocally injective homomorphismTheta graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

An algorithmic framework for locally constrained homomorphisms ⋮ List covering of regular multigraphs with semi-edges ⋮ Locally Injective Homomorphism to the Simple Weight Graphs ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

Cites Work

• On the complexity of H-coloring
• Covering regular graphs
• On the computational complexity of partial covers of theta graphs
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• NP completeness of the edge precoloring extension problem on bipartite graphs
• Partial covers of graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of Locally Injective Homomorphism to the Theta Graphs