Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width

Abstract

Two graphs are homomorphism indistinguishable over a graph class $\mathcal{F}$, denoted by $G{\equiv }_{\mathcal{F}}H$, if $\mathrm{hom}(F,G)=\mathrm{hom}(F,H)$ for all $F\in \mathcal{F}$ where $\mathrm{hom}(F,G)$ denotes the number of homomorphisms from $F$ to $G$. A classical result of Lovász shows that isomorphism between graphs is equivalent to homomorphism indistinguishability over the class of all graphs. More recently, there has been a series of works giving natural algebraic and/or logical characterizations for homomorphism indistinguishability over certain restricted graph classes. A class of graphs $\mathcal{F}$ is homomorphism-distinguishing closed if, for every $F\notin \mathcal{F}$, there are graphs $G$ and $H$ such that $G{\equiv }_{\mathcal{F}}H$ and $\mathrm{hom}(F,G)\ne \mathrm{hom}(F,H)$. Roberson conjectured that every class closed under taking minors and disjoint unions is homomorphism-distinguishing closed which implies that every such class defines a distinct equivalence relation between graphs. In this note, we confirm this conjecture for the classes ${\mathcal{T}}_k$, $k\ge 1$, containing all graphs of tree-width at most $k$. As an application of this result, we also characterize which subgraph counts are detected by the $k$-dimensional Weisfeiler-Leman algorithm. This answers an open question from [Arvind et al., J. Comput. Syst. Sci., 2020].

10 pages; second version adds a characterization of subgraph counts detected by WL