Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width

MaRDI QIDQ6433075zbMATH OpenFDO

Authors Daniel Neuen

Publication date 14 April 2023

Abstract: Two graphs are homomorphism indistinguishable over a graph class $mathcalF$, denoted by $Gequi{v}_{mathcalF}H$, if $operatornamehom(F,G)=operatornamehom(F,H)$ for all $FinmathcalF$ where $operatornamehom(F,G)$ denotes the number of homomorphisms from $F$ to $G$. A classical result of Lov'{a}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 $mathcalF$ is homomorphism-distinguishing closed if, for every $FotinmathcalF$, there are graphs $G$ and $H$ such that $Gequi{v}_{mathcalF}H$ and $operatornamehom(F,G)eqoperatornamehom(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$, $kgeq1$, 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].

This page was built for publication: Homomorphism-Distinguishing Closedness for Graphs of Bounded Tree-Width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6433075)