Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree

Understand

We introduce (weak) oddomorphisms of graphs which are homomorphisms with additional constraints based on parity.

• These maps turn out to have interesting properties (e.g., they preserve planarity), particularly in relation to homomorphism indistinguishability.
• Graphs $G$ and $H$ are *homomorphism indistinguishable* over a family $\mathcal{F}$ if $\hom(F,G) = \hom(F,H)$ for all $F \in \mathcal{F}$, where $\hom(F,G)$ is the number of homomorphisms from $F$ to $G$.
• A classical result of Lov\'{a}sz says that isomorphism is equivalent to homomorphism indistinguishability over the class of all graphs.