Min orderings and list homomorphism dichotomies for graphs and signed graphs

DOI10.1007/S00453-024-01228-1MaRDI QIDQ6582375zbMATH OpenFDO

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

Publication date 2 August 2024

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-024-01228-1

zbMATH Keywords

computational complexitydichotomygraph homomorphismsmin orderingsigned graphs

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Cites work

• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• A mathematical bibliography of signed and gain graphs and allied areas
• Approximation of minimum cost homomorphisms
• Bi‐arc graphs and the complexity of list homomorphisms
• Homomorphisms of signed graphs: an update
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• List homomorphism problems for signed trees
• List homomorphisms and circular arc graphs
• List homomorphisms to separable signed graphs
• Min orderings and list homomorphism dichotomies for signed and unsigned graphs
• Monotone monadic SNP and constraint satisfaction
• Nowhere-zero flows in signed graphs: a survey
• On orthogonal ray graphs
• On the complexity of H-coloring
• Permutation bigraphs and interval containments
• Representation characterizations of chordal bipartite graphs
• Signed graph coloring
• The complexity of signed graph and edge-coloured graph homomorphisms

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

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