Locally Injective Homomorphism to the Simple Weight Graphs

DOI10.1007/978-3-642-20877-5_46zbMath1331.68098OpenAlexW1521073631MaRDI QIDQ3010426

Ondřej Bílka, Marek Tesař, Bernard Lidický

Publication date: 1 July 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-20877-5_46

zbMATH Keywords

computational complexitylocally injective homomorphismweight graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Related Items

An algorithmic framework for locally constrained homomorphisms ⋮ List covering of regular multigraphs with semi-edges ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• Covering regular graphs
• On the computational complexity of partial covers of theta graphs
• Complexity of Locally Injective Homomorphism to the Theta Graphs
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• NP completeness of the edge precoloring extension problem on bipartite graphs
• Partial covers of graphs
• Monotone monadic SNP and constraint satisfaction
• The complexity of satisfiability problems