On the restricted homomorphism problem

DOI10.1016/J.DAM.2007.03.028MaRDI QIDQ948709zbMATH OpenOpenAlexFDO

Authors Richard C. Brewster, Timothy Graves

Publication date 17 October 2008

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

Full work available at URL https://doi.org/10.1016/j.dam.2007.03.028

zbMATH Keywords

computational complexitydigraph homomorphismhereditary hardnessrestricted homomorphism

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of restricted graph homomorphisms
• scientific article; zbMATH DE number 1208714
• A note on restricted H-colouring
• Hereditarily hard \(H\)-colouring problems
• scientific article; zbMATH DE number 4101217

Cites work

• scientific article; zbMATH DE number 1208714 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• A note on restricted H-colouring
• Circular chromatic number: A survey
• Density via duality.
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Hereditarily hard \(H\)-colouring problems
• On the Complexity of Ordered Colorings
• On the complexity of H-coloring
• On the complexity of the circular chromatic number
• Pair Labellings with Given Distance
• 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
• The chromatic number of the product of two 4-chromatic graphs is 4
• The complexity of restricted graph homomorphisms

Cited in

(2)

• Easy intruder deduction problems with homomorphisms
• Mixing homomorphisms, recolorings, and extending circular precolorings

This page was built for publication: On the restricted homomorphism problem

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