Dichotomy for bounded degree \(H\)-colouring

DOI10.1016/j.dam.2008.02.003zbMath1213.05100OpenAlexW2069703826MaRDI QIDQ1003659

Mark H. 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

graph colouringconstraint satisfaction problemdichotomybounded degree restriction

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

Unnamed Item ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture

Cites Work

• Unnamed Item
• Unnamed Item
• List homomorphisms of graphs with bounded degrees
• On the complexity of H-coloring
• Universality of \(A\)-mote graphs
• On colorings of graphs without short cycles
• The complexity of \(H\)-colouring of bounded degree graphs
• Note on projective graphs
• On highly ramsey infinite graphs
• On the complexity of the general coloring problem
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Colouring graphs when the number of colours is nearly the maximum degree