Abstract
The CSP dichotomy conjecture has been recently established, but a number of other dichotomy questions remain open, including the dichotomy classification of list homomorphism problems for signed graphs. Signed graphs arise naturally in many contexts, including for instance nowhere-zero flows for graphs embedded in non-orientable surfaces. For a fixed signed graph 饾惢^
H
^
, the list homomorphism problem asks whether an input signed graph 饾惡^
G
^ with lists 饾惪(饾懀)SUBSET OF OR EQUAL TO 聽饾憠(锟斤拷^),饾懀ELEMENT OF饾憠(锟斤拷^),
L
( v
)
SUBSET OF OR EQUAL TO
V
(
H
^
)
, v
ELEMENT OF
V
(
G
^
)
, admits a homomorphism f to 饾惢^
H
^ with all 饾憮(饾懀)ELEMENT OF饾惪(饾懀),饾懀ELEMENT OF饾憠(锟斤拷^) f
( v
)
ELEMENT OF
L
( v
)
, v
ELEMENT OF
V
(
G
^
)
.
Usually, a dichotomy classification is easier to obtain for list homomorphisms than for homomorphisms, but in the context of signed graphs a structural classification of the complexity of list homomorphism problems has not even been conjectured, even though the classification of the complexity of homomorphism problems is known.
Kim and Siggers have conjectured a structural classification in the special case of "weakly balanced" signed graphs. We confirm their conjecture for reflexive and irreflexive signed graphs; this generalizes previous results on weakly balanced signed trees, and weakly balanced separable signed graphs [1,2,3]. In the reflexive case, the result was first presented in [19], where the proof relies on a result in this paper. The irreflexive result is new, and its proof depends on first deriving a theorem on extensions of min orderings of (unsigned) bipartite graphs, which is interesting on its own.
