Homomorphisms of Sparse Signed Graphs

Source abstract

The notion of homomorphism of signed graphs, introduced quite recently, provides better interplay with the notion of minor and is thus of high importance in graph coloring. A newer, but equivalent, definition of homomorphisms of signed graphs, proposed jointly by the second and third authors of this paper and Thomas Zaslavsky, leads to a basic no-homomorphism lemma. According to this definition, a signed graph $(G, \sigma)$ admits a homomorphism to a signed graph $(H, \pi)$ if there is a mapping $\phi$ from the vertices and edges of $G$ to the vertices and edges of $H$ (respectively) which preserves adjacencies, incidences, and signs of closed walks (i.e., the product of the sign of their edges). For $ij=00, 01, 10, 11$, let $g_{ij}(G,\sigma)$ be the length of a shortest nontrivial closed walk of $(G, \sigma)$ which is, positive and of even length for $ij=00$, positive and of odd length for $ij=01$, negative and of even length for $ij=10$, negative and of odd length for $ij=11$. For each $ij$, if there is no nontrivial closed walk of the corresponding type, we let $g_{ij}(G, \sigma)=\infty$. If $G$ is bipartite, then $g_{01}(G,\sigma)=g_{11}(G,\sigma)=\infty$. In this case, $g_{10}(G,\sigma)$ is certainly realized by a cycle of $G$, and it will be referred to as the \emph{unbalanced-girth} of $(G,\sigma)$. It then follows that if $(G,\sigma)$ admits a homomorphism to $(H, \pi)$, then $g_{ij}(G, \sigma)\geq g_{ij}(H, \pi)$ for $ij \in \{00, 01,10,11\}$. Studying the restriction of homomorphisms of signed graphs on sparse families, in this paper we first prove that for any given signed graph $(H, \pi)$, there exists a positive value of $\epsilon$ such that, if $G$ is a connected graph of maximum average degree less than $2+\epsilon$, and if $\sigma$ is a signature of $G$ such that $g_{ij}(G, \sigma)\geq g_{ij}(H, \pi)$ for all $ij \in \{00, 01,10,11\}$, then $(G, \sigma)$ admits a homomorphism to $(H, \pi)$. For $(H, \pi)$ being the signed graph on $K_4$ with exactly one negative edge, we show that $\epsilon=\frac{4}{7}$ works and that this is the best possible value of $\epsilon$. For $(H, \pi)$ being the negative cycle of length $2g$, denoted $UC_{2g}$, we show that $\epsilon=\frac{1}{2g-1}$ works. As a bipartite analogue of the Jaeger-Zhang conjecture, Naserasr, Sopena and Rollovà conjectured in [Homomorphisms of signed graphs, {\em J. Graph Theory} 79 (2015)] that every signed bipartite planar graph $(G,\sigma)$ satisfying $g_{ij}(G,\sigma)\geq 4g-2$ admits a homomorphism to $UC_{2g}$. We show that $4g-2$ cannot be strengthened, and, supporting the conjecture, we prove it for planar signed bipartite graphs $(G,\sigma)$ satisfying the weaker condition $g_{ij}(G,\sigma)\geq 8g-2$. In the course of our work, we also provide a duality theorem to decide whether a 2-edge-colored graph admits a homomorphism to a certain class of 2-edge-colored signed graphs or not.