## Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree

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

*Theoretical Computer Science*, vol. 590, pp. 86-95, 2015.

[__DOI__][__Preprint__]

A preliminary version of this paper appeared in the proceedings of FCT 2013, 19th International Symposium on Fundamentals of Computation Theory (held on August 19-21, 2013 in Liverpool, United Kingdom), *Lecture Notes in Computer Science*, vol. 8070, pp. 121-132, 2013.

[__DOI__]

### Abstract:

A homomorphism from a graph *G* to a graph *H* is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of *G* is bijective, surjective, or injective, respectively. We prove that the problems of testing whether a given graph *G* allows a homomorphism to a given graph *H* that is locally bijective, surjective, or injective, respectively, are NP-complete, even in the restricted case where *G* has pathwidth at most 5, 4, or 2, respectively, or when both *G* and *H* have maximum degree 3. We complement these hardness results by showing that the three problems are polynomial-time solvable if *G* has bounded treewidth and in addition *G* or *H* has bounded maximum degree.