Artículo
Homomorphisms between graphs embedded in surfaces
Autor/es | Garijo Royo, Delia
![]() ![]() ![]() ![]() ![]() ![]() ![]() Goodall, Andrew Vena Cros, Lluís |
Fecha de publicación | 2024-05 |
Fecha de depósito | 2024-04-03 |
Publicado en |
|
Resumen | We extend the notion of graph homomorphism to cellularly embedded graphs (maps) by designing operations on vertices and edges that respect the surface topology; we thus obtain the first definition of map homomorphism that ... We extend the notion of graph homomorphism to cellularly embedded graphs (maps) by designing operations on vertices and edges that respect the surface topology; we thus obtain the first definition of map homomorphism that preserves both the combinatorial structure (as a graph homomorphism) and the topological structure of the surface (in particular, orientability and genus). Notions such as the core of a graph and the homomorphism order on cores are then extended to maps. We also develop a purely combinatorial framework for various topological features of a map such as the contractibility of closed walks, which in particular allows us to characterize map cores. We then show that the poset of map cores ordered by the existence of a homomorphism is connected and, in contrast to graph homomorphisms, does not contain any dense interval (so it is not universal for countable posets). Finally, we give examples of a pair of cores with an infinite number of cores between them, an infinite chain of gaps, and arbitrarily large antichains with a common homomorphic image. |
Agencias financiadoras | Czech Science Foundation Agència de Gestió d’Ajuts Universitaris i de Recerca |
Identificador del proyecto | PID2019-104129GB-I00/AEI/10.13039/501100011033
![]() 22-17398S ![]() BP2018-0030 ![]() |
Cita | Garijo Royo, D., Goodall, A. y Vena Cros, L. (2024). Homomorphisms between graphs embedded in surfaces. European Journal of Combinatorics, 118 (103936). https://doi.org/10.1016/j.ejc.2024.103936. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Homomorphisms between graphs ... | 648.2Kb | ![]() | Ver/ | |