The homomorphism order of signed graphs

Abstract

A signed graph \( (G, \sigma) \) is a graph \( G \) together with a mapping \( \sigma \) which assigns to each edge of \( G \) a sign, either positive or negative. The sign of a closed walk in \( (G, \sigma) \) is the product of the signs of its edges (considering multiplicity). Considering signs of closed walks as one of the key structures of signed graphs, a homomorphism of a signed graph \( (G, \sigma) \) to a signed graph \( (H, \pi) \) is defined to be a mapping that maps vertices to vertices, edges to edges, and that preserves incidences, adjacencies, and signs of closed walks. This is a recently defined notion, closely related to sign-preserving homomorphisms of signed graphs (or, equivalently, to homomorphisms of 2-edge-colored graphs), that helps, in particular, to establish a stronger connection between the theories of coloring and homomorphisms of graphs and the minor theory of graphs.

When there exists a homomorphism of \( (G, \sigma) \) to \( (H, \pi) \), one may write \( (G, \sigma) \to (H, \pi) \), thus extending the graph homomorphism order to a partial order on the classes of homomorphically equivalent signed graphs. In this work, studying this order, we prove that this order forms a lattice. That is to say, for each pair \( (G_1, \sigma_1) \) and \( (G_2, \sigma_2) \) of signed graphs, representing their respective classes, both their join and meet exist. While proving this result, we also show the existence of categorical products for signed graphs.