Min orderings and list homomorphism dichotomies for signed and unsigned graphs

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

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)

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

Mathematics Subject Classification ID

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

Related Items (2)

Min orderings and list homomorphism dichotomies for signed and unsigned graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• On the complexity of H-coloring
• Signed graph coloring
• A mathematical bibliography of signed and gain graphs and allied areas
• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• A characterization of weakly bipartite graphs
• A short proof of Guenin's characterization of weakly bipartite graphs
• List homomorphisms and circular arc graphs
• Homomorphisms of signed graphs: an update
• The complexity of signed graph and edge-coloured graph homomorphisms
• Approximation of Minimum Cost Homomorphisms
• Bi‐arc graphs and the complexity of list homomorphisms
• Monotone monadic SNP and constraint satisfaction
• 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

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