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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-09 Page: https://delphi.science/r/arxiv/2602.08738 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…