A complexity dichotomy for signed H-colouring

DOI10.1016/J.DISC.2018.06.026MaRDI QIDQ1660261zbMATH OpenOpenAlexFDO

Authors Richard C. Brewster, Mark 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

edge coloured graphhomomorphism complexitysigned graphswitching

Mathematics Subject Classification ID

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

Recommendations

• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• The complexity of signed graph and edge-coloured graph homomorphisms
• scientific article; zbMATH DE number 4008418
• On the complexity of H-coloring
• Hereditarily hard \(H\)-colouring problems

Cites work

• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Bi‐arc graphs and the complexity of list homomorphisms
• Colouring, constraint satisfaction, and complexity
• Edge-switching homomorphisms of edge-coloured graphs
• Homomorphisms and oriented colorings of equivalence classes of oriented graphs
• Homomorphisms of 2-edge-colored triangle-free planar graphs
• Homomorphisms of signed graphs
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• On the complexity of H-coloring
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• Polymorphisms of small digraphs
• Retractions to Pseudoforests
• Signed graphs
• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• The complexity of signed graph and edge-coloured graph homomorphisms
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)

Cited in

(15)

• Density of \(C_{-4}\)-critical signed graphs
• List homomorphism problems for signed trees
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Complexity of correspondence \(H\)-colourings
• Concepts of signed graph coloring
• The complexity of signed graph and edge-coloured graph homomorphisms
• scientific article; zbMATH DE number 7559391 (Why is no real title available?)
• The complexity of homomorphisms of signed graphs and signed constraint satisfaction
• 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
• Towards a dichotomy for the list switch homomorphism problem for signed graphs
• Min orderings and list homomorphism dichotomies for graphs and signed graphs
• A dichotomy theorem for -switchable H-colouring on m-edge-coloured graphs
• Complexity of planar signed graph homomorphisms to cycles

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

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