On the restricted homomorphism problem

DOI10.1016/J.DAM.2007.03.028zbMATH Open1151.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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• 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

Related Items (2)

Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings ⋮ Easy intruder deduction problems with homomorphisms

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)