The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction

DOI10.1007/978-3-642-54423-1_46zbMath1405.68137OpenAlexW1561235641MaRDI QIDQ5405070

Reza Naserasr, Florent Foucaud

Publication date: 31 March 2014

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

Full work available at URL: http://hdl.handle.net/2117/23412

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Related Items (12)

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ The complexity of signed graph and edge-coloured graph homomorphisms ⋮ A complexity dichotomy for signed \(\mathbf{H}\)-colouring ⋮ Relative clique number of planar signed graphs ⋮ Unnamed Item ⋮ Concepts of signed graph coloring ⋮ Unnamed Item ⋮ Relative Clique Number of Planar Signed Graphs ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ Homomorphisms of sparse signed graphs ⋮ Homomorphisms of Signed Graphs ⋮ List homomorphism problems for signed trees

This page was built for publication: The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction