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 illustrate this by classifying the complexity of irreflexive signed graphs in which the unicoloured edges form some simple structures, namely paths or cycles. The structure of the signed graphs in the polynomial cases is interesting, suggesting they may constitute a nice class of signed graphs analogous to the so-called bi-arc graphs (which characterize the polynomial cases of list homomorphisms to unsigned graphs).

翻译：我们从计算角度来考虑签名图形的同质性。 特别是, 我们研究列表同质性问题, 寻求输入签名的图形$( G,\\ sigma) 的同质性, 配有允许图像列表$L( v)\ subseteq V( H), v\ in V( G)$, 配有允许图像的列表 $L (v)\ subseteq V( H), 配有固定目标签名的图形$( H,\ pi) $ 。 类似的同质性问题的复杂性没有列表( 对应所有列表为$L( v) = V( H) $), 之前由 Brewster 和 Siggers 进行分类, 但列表版本仍然打开并看起来很困难 。 当$H 是树时, 我们通过对问题的复杂性进行分类来说明这个困难 。 我们开发的工具对于其它类型签名的图形的图形的分类是有用的, 我们通过对不易变式签名的图形的图形的复杂性进行分类, 即路径或周期。 签名的图形的图形的类中, 的图形的图形的图类中, 表示它们可能构成一个清晰的正统的正统的图案的图案的图。