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

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

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)

Cited In (31)

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

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)