Dichotomy for bounded degree \(H\)-colouring
type: Item
instance of: scholarly article
title: Dichotomy for bounded degree \(H\)-colouring
zbMATH Open document ID: 1213.05100
author: Mark Siggers
published in: Discrete Applied Mathematics
publication date: 2009-03-04T00:00:00Z
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5523147
zbMATH Keywords: constraint satisfaction problem
zbMATH Keywords: graph colouring
zbMATH Keywords: dichotomy
zbMATH Keywords: bounded degree restriction
MaRDI profile type: Publication
full work available at URL: j.dam.2008.02.003
OpenAlex ID: W2069703826
cites work: Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
cites work: List homomorphisms of graphs with bounded degrees
cites work: The complexity of \(H\)-colouring of bounded degree graphs
cites work: Universality of \(A\)-mote graphs
cites work: On the complexity of H-coloring
cites work: Q4828516
cites work: Note on projective graphs
cites work: On the complexity of the general coloring problem
cites work: Colouring graphs when the number of colours is nearly the maximum degree
cites work: On colorings of graphs without short cycles
cites work: Q3912037
cites work: On highly ramsey infinite graphs
DOI: 10.1016/J.DAM.2008.02.003
Recommended article: \(H\)-coloring dichotomy revisited
Recommended article: The complexity of \(H\)-colouring of bounded degree graphs
Recommended article: Q5091252
Recommended article: \(H\)-coloring degree-bounded (acyclic) digraphs
Recommended article: A New Proof of the H-Coloring Dichotomy
Recommended article: Logical Approaches to Computational Barriers
Recommended article: Colouring H-free graphs of bounded diameter.
Recommended article: Small H-Coloring Problems for Bounded Degree Digraphs
Recommended article: A note on restricted \(H\)-colouring
Recommended article: Complexity issues on bounded restrictive \(H\)-coloring
description: scientific article; zbMATH DE number 5523147