A complexity dichotomy for signed \(\mathbf{H}\)-colouring
type: Item
instance of: scholarly article
title: A complexity dichotomy for signed \(\mathbf{H}\)-colouring
zbMATH Open document ID: 1393.05108
author: Richard C. Brewster
author: Mark Siggers
published in: Discrete Mathematics
publication date: 2018-08-15T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C22
zbMATH DE Number: 6918734
zbMATH Keywords: signed graph
zbMATH Keywords: edge coloured graph
zbMATH Keywords: homomorphism complexity
zbMATH Keywords: switching
MaRDI profile type: Publication
full work available at URL: j.disc.2018.06.026
OpenAlex ID: W2883849606
cites work: The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
cites work: Q4993594
cites work: Polymorphisms of small digraphs
cites work: The complexity of signed graph and edge-coloured graph homomorphisms
cites work: Edge-switching homomorphisms of edge-coloured graphs
cites work: Bi‐arc graphs and the complexity of list homomorphisms
cites work: Retractions to Pseudoforests
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction
cites work: On the complexity of H-coloring
cites work: Colouring, constraint satisfaction, and complexity
cites work: Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
cites work: Homomorphisms and oriented colorings of equivalence classes of oriented graphs
cites work: Homomorphisms of Signed Graphs
cites work: Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs
cites work: A strong Mal'cev condition for locally finite varieties omitting the unary type
cites work: Signed graphs
DOI: 10.1016/J.DISC.2018.06.026
description: scientific article; zbMATH DE number 6918734