Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width
share
Two 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 note, 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].
READ FULL TEXT