Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

DOI10.1016/j.tcs.2015.01.028zbMath1430.68122arXiv1408.6676OpenAlexW2006186391MaRDI QIDQ2348037

Pim van 't Hof, Marek Tesař, Steven Chaplick, Daniël Paulusma, Jiří Fiala

Publication date: 10 June 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.6676

zbMATH Keywords

computational complexitybounded degreebounded treewidthlocally constrained graph homomorphisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Computing role assignments of split graphs ⋮ Parameterizing role coloring on forests ⋮ List covering of regular multigraphs ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ List covering of regular multigraphs with semi-edges ⋮ Role colouring graphs in hereditary classes ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing role assignments of proper interval graphs in polynomial time
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• The core of a graph
• A complete complexity classification of the role assignment problem
• Cantor--Bernstein type theorem for locally constrained graph homomorphisms
• Comparing universal covers in polynomial time
• On the complexity of H-coloring
• Finite common coverings of pairs of regular graphs
• Role colouring a graph
• Treewidth. Computations and approximations
• Covering regular graphs
• The complexity of \(H\)-colouring of bounded degree graphs
• On the computational complexity of partial covers of theta graphs
• Homomorphisms of derivative graphs
• How hard is it to determine if a graph has a 2-role assignment?
• Locally Constrained Homomorphisms on Graphs of Bounded Treewidth and Bounded Degree
• Complexity of Locally Injective Homomorphism to the Theta Graphs
• Locally Injective Homomorphism to the Simple Weight Graphs
• Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Constructing 5-Arc-Transitive Cubic Graphs
• Partial covers of graphs
• Graph Transformations
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The role assignment model nearly fits most social networks
• Fixed-parameter complexity of \(\lambda\)-labelings