Homomorphisms between graphs embedded in surfaces (extended abstract)

• Delia Garijo ^[1] ; Andrew Goodall ^[2] ; Lluís Vena ^[3]
  1. [1] Universidad de Sevilla

     Universidad de Sevilla

     Sevilla, España

     
  2. [2] Charles University in Prague

     Charles University in Prague

     Chequia

     
  3. [3] Universitat Politècnica de Catalunya

     Universitat Politècnica de Catalunya

     Barcelona, España

     

  Mostrar afiliaciones +
• Localización: Discrete Mathematics Days 2022 / Luis Felipe Tabera Alonso (ed. lit.) , 2022, ISBN 978-84-19024-02-2, págs. 141-146
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

  • A graph homomorphism can be realized as a sequence of vertex identifications followedby suppression of multiple edges. We extend this notion to cellularly embedded graphs inclosed surfaces (maps) in a way that preserves both the combinatorial structure of the graphand the topological structure of the surface. By restricting vertex identifications to thosethat can be performed while respecting the surface topology, we obtain a definition of maphomomorphism that preserves genus and orientability. Such notions as the core of a graphand the homomorphism order are then extended to maps. We characterize map cores via acombinatorial formulation of some contractible curves on the surface in which the graph isembedded. We also show that, in contrast to graph homomorphisms, the poset of map coresordered by the existence of a homomorphism does not contain any dense interval (so it isnot universal for countable posets), and give examples of a pair of cores with an infinitenumber of cores between them and of an infinite chain of gaps.