On the restricted homomorphism problem

DOI10.1016/j.dam.2007.03.028zbMath1151.68042OpenAlexW2028416100MaRDI QIDQ948709

Timothy Graves, Richard C. Brewster

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

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

Related Items (1)

Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings

Cites Work

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

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