The complexity of \(H\)-colouring of bounded degree graphs

DOI10.1016/S0012-365X(00)00009-1zbMath0956.05036OpenAlexW1988205260MaRDI QIDQ1579552

Jaroslav Nešetřil, Anna Galluccio, Pavol Hell

Publication date: 4 March 2001

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

Full work available at URL: https://doi.org/10.1016/s0012-365x(00)00009-1

zbMATH Keywords

NP-completenessbounded degree graphBrooks theorem\(H\)-colouring problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (16)

The complexity of signed graph and edge-coloured graph homomorphisms ⋮ List homomorphisms of graphs with bounded degrees ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Unnamed Item ⋮ Colouring, constraint satisfaction, and complexity ⋮ Unnamed Item ⋮ Graph partitions with prescribed patterns ⋮ Dichotomy for bounded degree \(H\)-colouring ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ Extension problems with degree bounds ⋮ Häggkvist-Hell graphs: A class of Kneser-colorable graphs ⋮ Homomorphisms of hexagonal graphs to odd cycles ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ Cuts and bounds ⋮ Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree ⋮ Counting \(H-\)colorings of partial \(k-\)trees

This page was built for publication: The complexity of \(H\)-colouring of bounded degree graphs