The complexity of H-colouring of bounded degree graphs

DOI10.1016/S0012-365X(00)00009-1zbMATH Open0956.05036OpenAlexW1988205260MaRDI QIDQ1579552FDOQ1579552

Authors A. Galluccio, Pavol Hell, J. Nešetřil

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)

Recommendations

• Complexity issues on bounded restrictive \(H\)-coloring
• scientific article; zbMATH DE number 1953088
• On the complexity of H-coloring
• scientific article; zbMATH DE number 4008418
• \(H\)-coloring degree-bounded (acyclic) digraphs
• Dichotomy for bounded degree \(H\)-colouring
• On the complexity of \(H\)-colouring planar graphs
• scientific article; zbMATH DE number 1983292
• The complexity of some graph colouring problems
• scientific article; zbMATH DE number 2156263

Cited in

(31)

• Closing complexity gaps for coloring problems on \(H\)-free graphs
• Dichotomy for bounded degree \(H\)-colouring
• Complexity of planar signed graph homomorphisms to cycles
• Colorings and homomorphisms of degenerate and bounded degree graphs
• Complexity of \(C_k\)-coloring in hereditary classes of graphs
• Cuts and bounds
• Extension problems with degree bounds
• The complexity of changing colourings with bounded maximum degree
• Complexity issues on bounded restrictive \(H\)-coloring
• Small \(H\)-coloring problems for bounded degree digraphs
• Graph partitions with prescribed patterns
• The complexity of colouring problems on dense graphs
• \(H\)-coloring degree-bounded (acyclic) digraphs
• scientific article; zbMATH DE number 4008418 (Why is no real title available?)
• Colouring, constraint satisfaction, and complexity
• Häggkvist-Hell graphs: A class of Kneser-colorable graphs
• scientific article; zbMATH DE number 7525468 (Why is no real title available?)
• On the complexity of H-coloring
• The complexity of infinite \(H\)-colouring
• \(H\)-free coloring on graphs with bounded tree-width
• Sparse \(H\)-colourable graphs of bounded maximum degree
• Homomorphisms of hexagonal graphs to odd cycles
• Counting \(H-\)colorings of partial \(k-\)trees
• The complexity of some graph colouring problems
• scientific article; zbMATH DE number 1983292 (Why is no real title available?)
• List homomorphisms of graphs with bounded degrees
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• The complexity of signed graph and edge-coloured graph homomorphisms
• The complexity of the \(T\)-coloring problem for graphs with small degree
• A note on restricted \(H\)-colouring
• Sparsification lower bounds for list \(H\)-coloring

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

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