Homomorphisms of signed graphs: An update
A signed graph is a graph together with an assignment of signs to the edges. A closed walk in a signed graph is said to be positive (negative) if it has an even (odd) number of negative edges, counting repetition. Recognizing the signs of closed walks as one of the key structural properties of a signed graph, we define a homomorphism of a signed graph $(G,\sigma)$ to a signed graph $(H, \pi)$ to be a mapping of vertices and edges of $G$ to (respectively) vertices and edges of $H$ which preserves incidence, adjacency and the signs of closed walks. In this work we first give a characterization of the sets of closed walks in a graph $G$ that correspond to the set of negative walks in some signed graph on $G$. We also give an easy algorithm for the corresponding decision problem. After verifying the equivalence between this definition and earlier ones, we discuss the relation between homomorphisms of signed graphs and those of 2-edge-colored graphs. Next we provide some basic no-homomorphism lemmas. These lemmas lead to a general method of defining chromatic number which is discussed at length. Finally, we list a few problems that are the driving force behind the study of homomorphisms of signed graphs.
NurtureToken New!

Token crowdsale for this paper ends in

Buy Nurture Tokens

Authors

Are you an author of this paper? Check the Twitter handle we have for you is correct.

Reza Naserasr (add twitter)
Eric Sopena (add twitter)
Thomas Zaslavsky (add twitter)
Category

Mathematics - Combinatorics

Subcategories
-
Ask The Authors

Ask the authors of this paper a question or leave a comment.

Read it. Rate it.
#1. Which part of the paper did you read?

#2. The paper contains new data or analyses that is openly accessible?
#3. The conclusion is supported by the data and analyses?
#4. The conclusion is of scientific interest?
#5. The result is likely to lead to future research?

Github
User:
None (add)
Repo:
None (add)
Stargazers:
0
Forks:
0
Open Issues:
0
Network:
0
Subscribers:
0
Language:
None
Youtube
Link:
None (add)
Views:
0
Likes:
0
Dislikes:
0
Favorites:
0
Comments:
0
Other
Sample Sizes (N=):
Inserted:
Words Total:
Words Unique:
Source:
Abstract:
None
09/15/19 06:05PM
15,060
2,415
Tweets
mathCObot: Reza Naserasr, Eric Sopena, Thomas Zaslavsky : Homomorphisms of signed graphs: An update https://t.co/U9nQZxey07 https://t.co/s7utFjffSS
Images
Related