Homomorphisms of sparse signed graphs
type: Item
instance of: scholarly article
title: Homomorphisms of sparse signed graphs
DOI: 10.37236/8478
author: Clément Charpentier
author: Reza Naserasr
author: Éric Sopena
published in: The Electronic Journal of Combinatorics
publication date: 2020-07-29T00:00:00Z
review text: Summary: 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 \textit{R. Naserasr} et al. [Eur. J. Comb. 91, Article ID 103222, 20 p. (2021; Zbl 1458.05098)], 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 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 \(\varepsilon\) such that, if \(G\) is a connected graph of maximum average degree less than \(2+\varepsilon \), 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…
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 7225783
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.37236/8478
OpenAlex ID: W3041680544
cites work: Homomorphisms of edge-colored graphs and Coxeter groups
cites work: The complexity of signed graph and edge-coloured graph homomorphisms
cites work: An introduction to the discharging method via graph coloring
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction
cites work: Q4828516
cites work: Q3682525
cites work: (2 + ?)-Coloring of planar graphs with large odd-girth
cites work: Mapping planar graphs into projective cubes
cites work: Q5747403
cites work: Homomorphisms of Signed Graphs
cites work: Homomorphisms of signed graphs: an update
cites work: Q4995309
cites work: Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs
cites work: Good and semi-strong colorings of oriented planar graphs
cites work: Signed graphs
cites work: Circular flows of nearly Eulerian graphs and vertex-splitting
description: scientific article; zbMATH DE number 7225783