Article ID Journal Published Year Pages File Type
471215 Computer Science Review 2008 15 Pages PDF
Abstract

A graph homomorphism is an edge preserving vertex mapping between two graphs. Locally constrained homomorphisms are those that behave well on the neighborhoods of vertices. If the neighborhood of any vertex of the source graph is mapped bijectively (injectively, surjectively) to the neighborhood of its image in the target graph, the homomorphism is called locally bijective (injective, surjective, respectively). We show that this view unifies issues studied before from different perspectives and under different names, such as graph covers, distance constrained graph labelings, or role assignments. Our survey provides an overview of applications, complexity results, related problems, and historical notes on locally constrained graph homomorphisms.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, ,