An Almost-tight Size Lower Bound for Bounded Treewidth Homomorphism-Distinguishability

Moritz Lichter, Harry Vinall-Smeeth

One way to compare two graphs $G_1,G_2$ is to check whether there is some graph $H$ in a graph class $\mathcal{H}$, such that the number of homomorphisms from $H$ to $G_1$ is not…