2026-07-23T21:47:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19763 2024-03-11T06:37:05Z ddc:004 open_access

Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width Neuen, Daniel homomorphism indistinguishability tree-width Weisfeiler-Leman algorithm subgraph counts 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 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Neuen 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.53 urn:nbn:de:0030-drops-197630 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.53 eng https://creativecommons.org/licenses/by/4.0/legalcode