Homomorphisms between graphs embedded in surfaces

DOI10.1016/J.EJC.2024.103936MaRDI QIDQ6201918zbMATH OpenOpenAlexFDO

Authors Delia Garijo, Andrew Goodall, Lluís Vena

Publication date 26 March 2024

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2305.03107

zbMATH Keywords

cellularly embedded graphscore of a graphhomomorphism order on cores

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: 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.

Recommendations

• Homomorphisms and amalgamation
• Finite dualities and map-critical graphs on a fixed surface
• The core of a graph
• Homomorphism complexes and \(k\)-cores
• Homomorphically full graphs

Cites work

• A Tutte polynomial for maps
• A Tutte polynomial for maps. II: The non-orientable case
• Distinguishing graphs by their left and right homomorphism profiles
• Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
• FOUNDATIONS OF THE THEORY OF MAPS ON SURFACES WITH BOUNDARY
• Fractal property of the graph homomorphism order
• Graph theory. Foreword by Crispin St. J. A. Nash-Williams.
• Graphs on surfaces
• scientific article; zbMATH DE number 3741426 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 3407696 (Why is no real title available?)
• N-DIMENSIONAL GENERALIZED COMBINATORIAL MAPS AND CELLULAR QUASI-MANIFOLDS
• On the surface duality of linear graphs
• Partition functions and a generalized coloring-flow duality for embedded graphs
• Reflection positivity, rank connectivity, and homomorphism of graphs
• Regular homomorphisms and regular maps
• Removal and contraction for \(n\)-dimensional generalized maps.
• The core of a graph
• Topological models for boundary representation: A comparison with \(n\)- dimensional generalized maps

This page was built for publication: Homomorphisms between graphs embedded in surfaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201918)