Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors

Two graphs $G$ and $H$ are homomorphism indistinguishable over a class of graphs $\mathcal{F}$ if for all graphs $F \in \mathcal{F}$ the number of homomorphisms from $F$ to $G$ equals the number of homomorphisms from $F$ to $H$. Many natural equivalence relations comparing graphs such as (quantum) isomorphism, spectral, and logical equivalences can be characterised as homomorphism indistinguishability relations over certain graph classes. In this article, the interplay of the properties of a graph class and its homomorphism indistinguishability relation are studied. As an application, self-complementarity, a property of logics on graphs satisfied by many well-studied logics, is identified. It is proven that the equivalence over a self-complementary logic admitting a characterisation as homomorphism indistinguishability relation can be characterised by homomorphism indistinguishability over a minor-closed graph class. Thereby, first evidences are provided for a possible connection between minors and homomorphism indistinguishability as conjectured by Roberson (2022).