The complexity of H-colouring of bounded degree graphs

DOI10.1016/S0012-365X(00)00009-1MaRDI QIDQ1579552zbMATH OpenOpenAlexFDO

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

\(H\)-colouring problembounded degree graphBrooks theoremNP-completeness

Mathematics Subject Classification ID

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

Review text

Let \(H\) be a fixed graph; an \(H\)-colouring of \(G\) is a mapping \(c:V(G)\rightarrow V(H)\) which preserves adjacency; an \(H\)-colouring of \(G\) is also called a homomorphism of \(G\) to \(H\). In this paper the complexity of the \(H\)-colouring problem restricted to graphs of bounded degree is investigated. For \(H\)-colouring of bounded degree graphs it is pointed out that there exist polynomial algorithms for several of these restricted colouring problems. A conjecture about the complexity of certain cases of the problem is proposed, which states that for graphs of chromatic number three, all situations which are not solvable by the colouring algorithm inherent in the theorem of Brooks are NP-complete. The conjecture is motivated by proving several supporting results.

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

(35)

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

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)