We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G,\sigma), equipped with lists L(v) \subseteq V(H), v \in V(G), of allowed images, to a fixed target signed graph (H,\pi). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L(v)=V(H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. We illustrate this difficulty by classifying the complexity of the problem when H is a (reflexive or irreflexive)tree . The tools we develop will be useful for classifications of other classes of signed graphs, and we mention some follow-up research of this kind; the classifications are surprisingly complex.
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G,\sigma), equipped with lists L(v) \subseteq V(H), v \in V(G), of allowed images, to a fixed target signed graph (H,\pi). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L(v)=V(H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. We illustrate this difficulty by classifying the complexity of the problem when H is a tree (with possible loops) . The tools we develop will be useful for classifications of other classes of signed graphs, and we mention some follow-up research of this kind; the classifications are surprisingly complex.
R
(reflexive or irreflexive)tree
tree (with possible loops)