Counting Homomorphisms to Trees Modulo a Prime

DOI10.1145/3460958zbMath1495.68175MaRDI QIDQ5868880

Karen Seidel, Andreas Göbel, J. A. Gregor Lagodzinski

Publication date: 24 September 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3460958

zbMATH Keywords

graph homomorphisms; complexity dichotomy; modular counting

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C30: Enumeration in graph theory

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)