Homomorphisms of Signed Graphs

作者：Naserasr Reza^*; Rollova Edita; Sopena Eric

来源：Journal of Graph Theory, 2015, 79(3): 178-212.

DOI：10.1002/jgt.21817

• signed graph
• coloring
• homomorphism
• minor
• Hadwiger's conjecture

A signed graph [G,sigma] is a graph G together with an assignment of signs + and - to all the edges of G where sigma is the set of negative edges. Furthermore [G,sigma 1] and [G,sigma 2] are considered to be equivalent if the symmetric difference of sigma(1) and sigma(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 [G,sigma] is said to map to [H,sigma 1] if there is an equivalent signed graph [G,sigma] of [G,sigma] and a mapping phi:V(G)V(H) such that (i) if xyE(G) then phi(x)phi(y)E(H) and (ii) xy sigma if and only if phi(x)phi(y)sigma 1. The chromatic number of a signed graph [G,sigma] can then be defined as the smallest order of a homomorphic image of [G,sigma]. 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.

• 出版日期2015-7