Name
Abstract | ||
|---|---|---|
We study homomorphism problems of signed graphs from a computational point of view. A signed graph (G,Σ) is a graph G where each edge is given a sign, positive or negative; Σ⊆E(G) denotes the set of negative edges. Thus, (G,Σ) is a 2-edge-coloured graph with the property that the edge-colours, {+,−}, form a group under multiplication. Central to the study of signed graphs is the operation of switching at a vertex, that results in changing the sign of each incident edge. We study two types of homomorphisms of a signed graph (G,Σ) to a signed graph (H,Π): ec-homomorphisms and s-homomorphisms. Each is a standard graph homomorphism of G to H with some additional constraint. In the former, edge-signs are preserved. In the latter, edge-signs are preserved after the switching operation has been applied to a subset of vertices of G. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.disc.2016.08.005 | Discrete Mathematics |
Keywords | DocType | Volume |
Signed graph,Edge-coloured graph,Graph homomorphism,Dichotomy theorem | Journal | 340 |
Issue | ISSN | Citations |
2 | 0012-365X | 1 |
PageRank | References | Authors |
0.35 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard C. Brewster | 1 | 10 | 3.37 |
| Florent Foucaud | 2 | 122 | 19.58 |
| Pavol Hell | 3 | 2638 | 288.75 |
| Reza Naserasr | 4 | 154 | 23.98 |