The complexity of signed graph and edge-coloured graph homomorphisms

Richard C. Brewster, Florent Foucaud, Pavol Hell +1

We study homomorphism problems of signed graphs from a computational point of view. A signed graph $(G,\Sigma )$ is a graph $G$ where each edge is given a sign, positive or negative; $Σ\…