Towards a dichotomy for the list switch homomorphism problem for signed graphs

DOI10.5666/KMJ.2023.63.3.355MaRDI QIDQ6185533zbMATH OpenFDO

Authors Hyobeen Kim, Mark Siggers

Publication date 29 January 2024

zbMATH Keywords

signed graphswitchinglist colouringedge coloured graphhomomorphism complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Coloring of graphs and hypergraphs (05C15)

Recommendations

• The complexity of signed graph and edge-coloured graph homomorphisms
• List homomorphism problems for signed trees
• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Complexity of planar signed graph homomorphisms to cycles

Cites work

• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• A proof of the CSP dichotomy conjecture
• Bi‐arc graphs and the complexity of list homomorphisms
• Complexity of conservative constraint satisfaction problems
• Homomorphisms of signed graphs
• Interval-like graphs and digraphs
• List homomorphism problems for signed trees
• List homomorphisms to reflexive graphs
• Min orderings and list homomorphism dichotomies for signed and unsigned graphs
• On the complexity of H-coloring
• On the notion of balance of a signed graph
• Signed graphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• The complexity of signed graph and edge-coloured graph homomorphisms

Cited in

(1)

• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity

This page was built for publication: Towards a dichotomy for the list switch homomorphism problem for signed graphs

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