Cantor--Bernstein type theorem for locally constrained graph homomorphisms (Q852701): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.ejc.2006.06.003 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2064788829 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4017175 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4770409 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coverings and minors: Application to local computations in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Role colouring a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Partial covers of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fixed-parameter complexity of \(\lambda\)-labelings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3757929 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4373685 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4223772 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4472519 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Finite common coverings of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5534009 / rank | |||
Normal rank |
Latest revision as of 23:01, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Cantor--Bernstein type theorem for locally constrained graph homomorphisms |
scientific article |
Statements
Cantor--Bernstein type theorem for locally constrained graph homomorphisms (English)
0 references
15 November 2006
0 references
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)].
0 references
locally injective
0 references
locally surjective
0 references
locally bijective
0 references