Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs

Daniel Neuen, Tim Seppelt

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 o…