Complexity of homomorphisms to direct products of graphs

DOI10.1016/S0020-0190(01)00225-3zbMath1032.68084OpenAlexW2004356443MaRDI QIDQ1603497

Judit Büki, Csaba Szabó

Publication date: 14 July 2002

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00225-3

zbMATH Keywords

Computational complexityGraph homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On the extension of vertex maps to graph homomorphisms

Cites Work

• List homomorphisms of graphs with bounded degrees
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• Absolute retracts of bipartite graphs
• Monotone monadic SNP and constraint satisfaction