List homomorphisms to separable signed graphs

DOI10.1016/J.TCS.2024.114580MaRDI QIDQ6439891zbMATH OpenFDO

Authors Jan Bok, Richard C. Brewster, Tomás Feder, Pavol Hell, Nikola Jedličková

Publication date 10 June 2023

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114580

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees cite{mfcs} and reflexive signed graphs cite{ks}. Irreflexive signed graphs are in a certain sense the heart of the problem, as noted by a recent paper of Kim and Siggers. We focus on a special class of irreflexive signed graphs, namely those in which the unicoloured edges form a spanning path or cycle, which we call separable signed graphs. We classify the complexity of list homomorphisms to these separable signed graphs; we believe that these signed graphs will play an important role for the general resolution of the irreflexive case. We also relate our results to a conjecture of Kim and Siggers concerning the special case of weakly balanced irreflexive signed graphs; we have proved the conjecture in another paper, and the present results add structural information to that topic.

This page was built for publication: List homomorphisms to separable signed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439891)