Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Journal of Graph The...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Journal of Graph Theory
Article . 2014 . Peer-reviewed
License: Wiley Online Library User Agreement
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2015
Data sources: zbMATH Open
DBLP
Article
Data sources: DBLP
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Homomorphisms of Signed Graphs

Homomorphisms of signed graphs
Authors: Reza Naserasr; Edita Rollová; Éric Sopena;

Homomorphisms of Signed Graphs

Abstract

AbstractA signed graph is a graph G together with an assignment of signs + and − to all the edges of G where Σ is the set of negative edges. Furthermore and are considered to be equivalent if the symmetric difference of Σ1 and Σ2 is an edge cut of G. Naturally arising from matroid theory, several notions of graph theory, such as the theory of minors and the theory of nowhere‐zero flows, have been already extended to signed graphs. In an unpublished manuscript, B. Guenin introduced the notion of signed graph homomorphisms where he showed how some well‐known conjectures can be captured using this notion. A signed graph is said to map to if there is an equivalent signed graph of and a mapping such that (i) if then and if and only if . The chromatic number of a signed graph can then be defined as the smallest order of a homomorphic image of . Capturing the notion of graph homomorphism order, signed graph homomorphisms provide room for extensions and strengthenings of most homomorphism and coloring theories on graphs. Thus this paper is the first general study of signed graph homomorphisms. In this work, our focus would be on the relation of homomorphisms of signed graphs with minors of signed graphs. After a thorough introduction to the concept we show that the notion of signed graph homomorphism on the set of signed graphs whose underlying graph is bipartite already captures the standard notion of graph homomorphism. We prove that the largest planar signed clique is of order 8. For the maximum chromatic number of planar signed graphs we give the lower bound of 10 and the upper bound of 48. We determine this maximum for some other families such as outerplanar signed graphs. Finally, reformulating Hadwiger's conjecture in the language of homomorphism of signed graphs whose underlying graph is bipartite, we show that while some stronger form of the conjecture holds for small chromatic number, such strengthening of the conjecture would not hold for large chromatic numbers. This could be regarded as a first indication that perhaps Hadwiger's conjecture only holds for small chromatic numbers.

Keywords

signed graph, homomorphism, minor, Structural characterization of families of graphs, coloring, Signed and weighted graphs, Hadwiger's conjecture

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    49
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 10%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
49
Top 10%
Top 10%
Top 10%
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!