{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:25:14Z","timestamp":1759335914450,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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).\u00a0 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)$.\r\nIt 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\\}$.\r\nStudying 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$,\u00a0and 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)$.\r\nFor $(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.\u00a0\r\nAs a bipartite analogue of the Jaeger-Zhang conjecture, Naserasr, Sopena and Rollov\u00e0 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$.\r\nIn 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.<\/jats:p>","DOI":"10.37236\/8478","type":"journal-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T01:56:36Z","timestamp":1594259796000},"source":"Crossref","is-referenced-by-count":4,"title":["Homomorphisms of Sparse Signed Graphs"],"prefix":"10.37236","volume":"27","author":[{"given":"Cl\u00e9ment","family":"Charpentier","sequence":"first","affiliation":[]},{"given":"Reza","family":"Naserasr","sequence":"additional","affiliation":[]},{"given":"\u00c9ric","family":"Sopena","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2020,7,10]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v27i3p6\/8122","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v27i3p6\/8122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T01:56:36Z","timestamp":1594259796000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v27i3p6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,10]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2020,7,9]]}},"URL":"https:\/\/doi.org\/10.37236\/8478","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2020,7,10]]},"article-number":"P3.6"}}