Dichotomy for bounded degree H-colouring

DOI10.1016/J.DAM.2008.02.003MaRDI QIDQ1003659zbMATH OpenOpenAlexFDO

Authors Mark Siggers

Publication date 4 March 2009

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

Full work available at URL https://doi.org/10.1016/j.dam.2008.02.003

zbMATH Keywords

bounded degree restrictionconstraint satisfaction problemdichotomygraph colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• H-coloring dichotomy revisited
• The complexity of \(H\)-colouring of bounded degree graphs
• scientific article; zbMATH DE number 7561584
• \(H\)-coloring degree-bounded (acyclic) digraphs
• A new proof of the \(H\)-coloring dichotomy
• Logical Approaches to Computational Barriers
• Colouring H-free graphs of bounded diameter.
• Small \(H\)-coloring problems for bounded degree digraphs
• A note on restricted H-colouring
• Complexity issues on bounded restrictive H-coloring

Cites work

• Colouring graphs when the number of colours is nearly the maximum degree
• scientific article; zbMATH DE number 3723879 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• List homomorphisms of graphs with bounded degrees
• Note on projective graphs
• On colorings of graphs without short cycles
• On highly ramsey infinite graphs
• On the complexity of H-coloring
• On the complexity of the general coloring problem
• The complexity of \(H\)-colouring of bounded degree graphs
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Universality of \(A\)-mote graphs

Cited in

(13)

• A combinatorial constraint satisfaction problem dichotomy classification conjecture
• The complexity of \(H\)-colouring of bounded degree graphs
• ℋ-Colouring Dichotomy in Proof Complexity
• scientific article; zbMATH DE number 1983292 (Why is no real title available?)
• scientific article; zbMATH DE number 932194 (Why is no real title available?)
• Small \(H\)-coloring problems for bounded degree digraphs
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Logical Approaches to Computational Barriers
• Colorings and homomorphisms of degenerate and bounded degree graphs
• Sparsification lower bounds for list \(H\)-coloring
• Sparsification lower bounds for list H-coloring
• \(H\)-coloring degree-bounded (acyclic) digraphs
• Complexity of planar signed graph homomorphisms to cycles

This page was built for publication: Dichotomy for bounded degree \(H\)-colouring

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