{"id":"arxiv/2602.08738","url":"https://arxiv.org/abs/2602.08738","tags":["math.CO"],"score":0,"title":"Homomorphism counting for immersion-closed classes is not isomorphism","domain":"math.CO","source":"arxiv","authors":["Andrea Jiménez","Benjamin Moore","Daniel A. Quiroz","Youngho Yoo"],"reviews":0,"subject":"math.CO","summary":"Lovász proved that two graphs $G$ and $H$ are isomorphic if $\\hom(K,G) = \\hom(K,H)$ for all graphs $K$, where $\\hom(G_1,G_2)$ denotes the number of homomorphisms from $G_1$ to $G_2$. Dvořák showed that it suffices to count homomorphisms from all $2$-degenerate graphs $K$. On the other hand, for several interesting graph classes $\\mathcal{M}$, it has been shown that there exist non-isomorphic graphs $G$ and $H$ such that $\\hom(K,G)=\\hom(K,H)$ for all $K\\in \\mathcal{M}$. Most such classes are minor-closed and Roberson conjectured that every proper minor-closed graph class $\\mathcal{M}$ has the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-09","reactions":{}}