Min orderings and list homomorphism dichotomies for signed and unsigned graphs

DOI10.1007/978-3-031-20624-5_31arXiv2206.01068OpenAlexW4312849998MaRDI QIDQ6109028FDOQ6109028

Pavol Hell, Richard C. Brewster, Jan Bok, Arash Rafiey, Nikola Jedličková

Publication date: 26 July 2023

Published in: LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

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 $widehatH$, the list homomorphism problem asks whether an input signed graph $widehatG$ with lists $L(v)subseteqV(widehatH),vinV(widehatG),$ admits a homomorphism $f$ to $widehatH$ with all $f(v)inL(v),vinV(widehatG)$. 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 cite{separable,trees}. In the reflexive case, the result was first presented in cite{KS}, with the proof using some of our results included in this paper. In fact, here we present our full proof, as an alternative to the proof in cite{KS}. In particular, we provide direct polynomial algorithms where previously algorithms relied on general dichotomy theorems. The irreflexive results are new, and their proof depends on first deriving a theorem on extensions of min orderings of (unsigned) bipartite graphs, which is interesting on its own. [shortened, full abstract in PDF]

Full work available at URL: https://arxiv.org/abs/2206.01068

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx)

Cites Work

• Signed graph coloring
• A mathematical bibliography of signed and gain graphs and allied areas
• Title not available (Why is that?)
• On the complexity of H-coloring
• Monotone monadic SNP and constraint satisfaction
• A characterization of weakly bipartite graphs
• List homomorphisms and circular arc graphs
• Approximation of Minimum Cost Homomorphisms
• Bi‐arc graphs and the complexity of list homomorphisms
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• A short proof of Guenin's characterization of weakly bipartite graphs
• The complexity of signed graph and edge-coloured graph homomorphisms
• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• Homomorphisms of signed graphs: an update
• Title not available (Why is that?)
• Nowhere-zero flows in signed graphs: A survey
• List homomorphisms to separable signed graphs
• Min orderings and list homomorphism dichotomies for signed and unsigned graphs

Cited In (3)

• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• Title not available (Why is that?)
• Min orderings and list homomorphism dichotomies for signed and unsigned graphs

This page was built for publication: Min orderings and list homomorphism dichotomies for signed and unsigned graphs

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