Neuen, DanielDanielNeuen2025-09-042025-09-042024https://media.suub.uni-bremen.de/handle/elib/22317https://doi.org/10.26092/elib/4267Two graphs are homomorphism indistinguishable over a graph class 𝐅, denoted by G ≡_𝐅 H, if hom(F,G) = hom(F,H) for all F ∈ 𝐅 where 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 𝐅 is homomorphism-distinguishing closed if, for every F ∉ 𝐅, there are graphs G and H such that G ≡_𝐅 H and hom(F,G) ≠ 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 work, we confirm this conjecture for the classes 𝒯_k, k ≥ 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].enhttps://creativecommons.org/licenses/by/4.0/homomorphism indistinguishabilitytree-widthWeisfeiler-Leman algorithmsubgraph counts000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, SystemeText::Konferenzveröffentlichung::Tagungsband::Konferenzbeitrag10.26092/elib/4267urn:nbn:de:gbv:46-elib223178