Homomorphisms of sparse signed graphs
The electronic journal of combinatorics, Tome 27 (2020) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/8478
Classification : 05C22, 05C15, 05C38

Clément Charpentier    ; Reza Naserasr  1   ; Éric Sopena  2

1 université PARIS DIDEROT
2 Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence.
@article{10_37236_8478,
     author = {Cl\'ement Charpentier and Reza Naserasr and \'Eric Sopena},
     title = {Homomorphisms of sparse signed graphs},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {3},
     doi = {10.37236/8478},
     zbl = {1508.05073},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8478/}
}
TY  - JOUR
AU  - Clément Charpentier
AU  - Reza Naserasr
AU  - Éric Sopena
TI  - Homomorphisms of sparse signed graphs
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8478/
DO  - 10.37236/8478
ID  - 10_37236_8478
ER  - 
%0 Journal Article
%A Clément Charpentier
%A Reza Naserasr
%A Éric Sopena
%T Homomorphisms of sparse signed graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8478/
%R 10.37236/8478
%F 10_37236_8478
Clément Charpentier; Reza Naserasr; Éric Sopena. Homomorphisms of sparse signed graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 3. doi: 10.37236/8478

Cité par Sources :