The restrictive \(H\)-coloring problem

DOI10.1016/j.dam.2004.01.018zbMath1062.05055OpenAlexW1986011439MaRDI QIDQ1764813

Dimitrios M. Thilikos, Maria J. Serna, Josep Diaz

Publication date: 22 February 2005

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

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

zbMATH Keywords

NP-completenessgraph homomorphismpolynomial algorithmsrestrictive \(H\)-coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Compactors for parameterized counting problems ⋮ In praise of homomorphisms ⋮ Complexity issues on bounded restrictive \(H\)-coloring ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Efficient algorithms for counting parameterized list \(H\)-colorings ⋮ \(H\)-colouring \(P_t\)-free graphs in subexponential time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Finding good approximate vertex and edge partitions is NP-hard
• List homomorphisms and circular arc graphs
• Bi‐arc graphs and the complexity of list homomorphisms

This page was built for publication: The restrictive \(H\)-coloring problem