Complexity issues on bounded restrictive \(H\)-coloring

DOI10.1016/j.disc.2005.12.058zbMath1119.05042OpenAlexW2127890825MaRDI QIDQ2370448

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

Publication date: 26 June 2007

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

Full work available at URL: https://doi.org/10.1016/j.disc.2005.12.058

zbMATH Keywords

NP-completeparameterizationcounting problemsrestrictive \(H\)-coloringrestrictive list \(H\)-coloring{\#}P-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

Compactors for parameterized counting problems, In praise of homomorphisms, Efficient algorithms for counting parameterized list \(H\)-colorings

Cites Work

• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• The restrictive \(H\)-coloring problem
• List homomorphisms and circular arc graphs
• Bi‐arc graphs and the complexity of list homomorphisms
• Algorithms – ESA 2004
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item