Cantor--Bernstein type theorem for locally constrained graph homomorphisms (Q852701): Difference between revisions

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)].