A complexity dichotomy for signed \(\mathbf{H}\)-colouring

DOI10.1016/j.disc.2018.06.026zbMath1393.05108OpenAlexW2883849606MaRDI QIDQ1660261

Richard C. Brewster, Mark H. Siggers

Publication date: 15 August 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2018.06.026

zbMATH Keywords

signed graphswitchingedge coloured graphhomomorphism complexity

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Related Items (11)

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ Complexity of correspondence \(H\)-colourings ⋮ The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial ⋮ List homomorphisms to separable signed graphs ⋮ Min orderings and list homomorphism dichotomies for signed and unsigned graphs ⋮ Unnamed Item ⋮ Concepts of signed graph coloring ⋮ Unnamed Item ⋮ Density of \(C_{-4}\)-critical signed graphs ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ List homomorphism problems for signed trees

Cites Work

• Unnamed Item
• Unnamed Item
• Colouring, constraint satisfaction, and complexity
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Edge-switching homomorphisms of edge-coloured graphs
• On the complexity of H-coloring
• Signed graphs
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• The complexity of signed graph and edge-coloured graph homomorphisms
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• Retractions to Pseudoforests
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Bi‐arc graphs and the complexity of list homomorphisms
• Homomorphisms of Signed Graphs
• Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs
• The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction

This page was built for publication: A complexity dichotomy for signed \(\mathbf{H}\)-colouring