{"id":"arxiv/2601.18602","url":"https://arxiv.org/abs/2601.18602","tags":["math.CO","cs.DM","cs.LO"],"score":0,"title":"Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs","domain":"math.CO","source":"arxiv","authors":["Daniel Neuen","Tim Seppelt"],"reviews":0,"subject":"math.CO","summary":"Lovász (1967) showed that two graphs $G$ and $H$ are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs, i.e., $G$ and $H$ admit the same number of number of homomorphisms from every graph $F$. Subsequently, a substantial line of work studied homomorphism indistinguishability over restricted graph classes. For example, homomorphism indistinguishability over minor-closed graph classes $\\mathcal{F}$ such as the class of planar graphs, the class of graphs of treewidth $\\leq k$, pathwidth $\\leq k$, or treedepth $\\leq k$, was shown to be equivalent to quantum…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-26","reactions":{}}