Complexity of locally injective homomorphism to the Theta graphs

DOI10.1007/978-3-642-19222-7_33MaRDI QIDQ3000520zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On the computational complexity of partial covers of theta graphs
• Complexity of locally-injective homomorphisms to tournaments
• The complexity of locally injective homomorphisms
• Locally injective homomorphism to the simple weight graphs
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy

Cites work

• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 1236360 (Why is no real title available?)
• scientific article; zbMATH DE number 1107736 (Why is no real title available?)
• scientific article; zbMATH DE number 2038757 (Why is no real title available?)
• scientific article; zbMATH DE number 2080268 (Why is no real title available?)
• scientific article; zbMATH DE number 2081019 (Why is no real title available?)
• Covering regular graphs
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• NP completeness of the edge precoloring extension problem on bipartite graphs
• On the complexity of H-coloring
• On the computational complexity of partial covers of theta graphs
• Partial covers of graphs

Cited in

(7)

• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• Locally injective homomorphism to the simple weight graphs
• An algorithmic framework for locally constrained homomorphisms
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• The complexity of locally injective homomorphisms
• An algorithmic framework for locally constrained homomorphisms
• List covering of regular multigraphs with semi-edges

This page was built for publication: Complexity of locally injective homomorphism to the Theta graphs

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