A homomorphism from a graph $F$ to a graph $G$ is a map $V(F) \to V(G)$ sending adjacent vertices to adjacent vertices. We write $\hom(F, G)$ for the number of such maps.

Two graphs $G$ and $H$ are homomorphism indistinguishable over a class $\mathcal{F}$, written $G \equiv_{\mathcal{F}} H$, if $\hom(F, G) = \hom(F, H)$ for every $F \in \mathcal{F}$.

Since $\hom(F, -)$ is an isomorphism invariant, this is a graph isomorphism relaxation, and it is defined as one: $homIndRel \mathcal{F}$ is the relaxation itself, and $G \equiv_{\mathcal{F}} H$ is notation for the relation it carries.

The homomorphism distinguishing closure of a graph class $\mathcal{F}$ is

the largest graph class whose homomorphism indistinguishability relation coincides with that of $\mathcal{F}$. A class is homomorphism distinguishing closed if it equals its own closure, i.e. if adding any further graph strictly refines its homomorphism indistinguishability relation.

Two products of simple graphs, both on the product $V(G) \times V(H)$ of the vertex sets.

In the categorical product $G \times H$, the pairs $gh$ and $g'h'$ are adjacent when $gg' \in E(G)$ and $hh' \in E(H)$. It is the product in the category of graphs and graph homomorphisms, whence $\hom(F, G \times H) = \hom(F, G)\hom(F, H)$; it also goes by tensor, Kronecker, weak or conjunction product.

In the lexicographic product $G \cdot H$, the pairs $gh$ and $g'h'$ are adjacent when $gg' \in E(G)$, or else $g = g'$ and $hh' \in E(H)$.

A partition into connected parts of a simple graph $F$ is a partition $\mathcal{R}$ of $V(F)$ such that the subgraph $F[R]$ induced by every class $R \in \mathcal{R}$ is connected.

A graph $K$ is obtained from a simple graph $F$ by contracting edges when the vertices of $K$ are the classes of a partition $\mathcal{R}$ of $V(F)$ into parts inducing connected subgraphs, two distinct classes being adjacent in $K$ exactly when $F$ joins a vertex of one to a vertex of the other. In the notation of the paper, $K \cong F/\mathcal{R}$.

Five closure properties of a class $\mathcal{F}$ of finite simple graphs.

$\mathcal{F}$ is closed under taking summands if $F_1 + F_2 \in \mathcal{F}$ implies $F_1 \in \mathcal{F}$ and $F_2 \in \mathcal{F}$, where $+$ denotes disjoint union, and union-closed if conversely $F_1, F_2 \in \mathcal{F}$ implies $F_1 + F_2 \in \mathcal{F}$. It is minor-closed if every minor of a member is a member.

It is closed under taking induced subgraphs if every induced subgraph of a member is a member, and closed under contracting edges if every graph obtained from a member by contracting edges is a member.

Five properties an equivalence relation $\equiv$ on finite simple graphs may have.

It is preserved under disjoint unions if $G \equiv G'$ and $H \equiv H'$ imply $G + H \equiv G' + H'$, and preserved under categorical products if $G \equiv H$ implies $G \times K \equiv H \times K$ for every graph $K$. It is preserved under taking complements if $G \equiv H$ implies $\overline{G} \equiv \overline{H}$; since complementation is an involution and $\equiv$ is symmetric, this one implication already gives the biconditional of the paper.

It is preserved under left lexicographic products if $H \equiv H'$ implies $G \cdot H \equiv G \cdot H'$ for every graph $G$, and preserved under right lexicographic products if $G \equiv G'$ implies $G \cdot H \equiv G' \cdot H$ for every graph $H$.

A graph isomorphism relaxation is an equivalence relation on finite simple graphs that is coarser than isomorphism: isomorphic graphs are related, and the relation is symmetric and transitive.

A loop graph is a graph in which loops are allowed: a symmetric, not necessarily irreflexive, relation on a vertex type. Simple graphs are the loopless case, and a loop graph without loops is a simple graph again. A homomorphism of loop graphs sends adjacent vertices to adjacent vertices, so a loop is sent to a loop and an edge to an edge or to a loop, and $\hom(X, Y)$ counts these maps as for simple graphs. Besides homomorphisms and isomorphisms, loop graphs carry here the full complement $\widehat{X}$, which replaces every edge by a non-edge and every loop by a non-loop, the sub-loop-graph induced on a set of vertices, and the edge set, which for a loop graph may contain a pair $vv$, one for each loop.

Loops arise from two constructions on simple graphs. The looped graph $G^\circ$ is obtained from a simple graph $G$ by adding a loop at every vertex; the complement then factors as $\overline{G} = \widehat{G^\circ}$, which is what makes a two-step expansion of homomorphism counts into a complement possible.

The other is a quotient. For a simple graph $F$ and a set $L$ of unordered pairs of vertices, the contraction quotient $F \oslash L$ has as vertices the connected components of the graph on $V(F)$ with edge set $L$, and joins two of them when some edge of $E(F) \setminus L$ joins a vertex of the one to a vertex of the other. It is a graph obtained from $F$ by contracting the edges of $L$ whenever it is loopless; in general it is not, carrying a loop at a component for every edge of $E(F) \setminus L$ with both endpoints inside it, which is why loops must be allowed here.

Two operations on simple graphs accompany these: the spanning subgraph $F_s$, which keeps all vertices of $F$ and those of its edges that lie in a set $s$, and the passage from a set of edges of $F$ to the underlying set of unordered pairs.