Cantor--Bernstein type theorem for locally constrained graph homomorphisms (Q852701)

The graphs considered in this paper are understood to be undirected and without loops or multiple edges. For graphs \(G\) and \(H\), a mapping \(f:V(G) \rightarrow V(H)\) is called a homomorphism if adjacent vertices of \(G\) are mapped onto adjacent vertices of \(H\). A homomorphism \(f:V(G) \rightarrow V(H)\) is locally injective if, for every \(u \in V(G)\), the neighbors of \(u\) are mapped injectively in the set of neighbors of \(f(u)\); analogously, the terms locally surjective and locally bijective are defined. The main result of the paper is the following theorem which is motivated by the Cantor-Bernstein theorem. For a graph \(G\) (finite or infinite) and a finite connected graph \(H\), suppose that there is a locally surjective homomorphism \(g:G \rightarrow H\) and a locally injective homomorphism \(h:G \rightarrow H\). Then \(g\) and \(h\) are locally bijective. This generalizes and unifies previous results of \textit{P.~Kristiansen} and \textit{J. A.~Telle} [Lect. Notes Comput. Sci. 1969, 456--466 (2000; Zbl 1044.68129)] and \textit{J.~Fiala} and \textit{J.~Kratochvíl} [Discuss. Math., Graph Theory 22, 89--99 (2002; Zbl 1017.05094)].