|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Homomorphisms of signed graphs: An update | | Reza Naserasr
; Eric Sopena
; Thomas Zaslavsky
; | | Date: |
13 Sep 2019 | | Abstract: | 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. | | Source: | arXiv, 1909.5982 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER