The bounded expansion characterization for first-order definable colorings

Let $\mathcal C$ be a hereditary addable topologically closed class of graphs. For a graph $H$, an $H$-coloring of a graph $G$ means a homomorphism $G\rightarrow H$; a graph class is first-order definable when it is defined by a first-order formula. The odd-girth of a graph is the length of its shortest odd cycle, and a $p$-subdivision is obtained by replacing every edge by a path of length $p+1$.

Bounded expansion characterization. The following properties are equivalent: for every integer $p$ there is a non-bipartite graph $H_p$ of odd-girth strictly greater than $2p+1$ and a first-order definable class $\mathcal D_p$ such that, for every graph $G\in\mathcal C$,

$$(G\vDash \Phi_p)\quad\iff\quad (G\rightarrow H_p)$$

for some formula $\Phi_p$, and the class $\mathcal C$ has bounded expansion.

This conjecture proposes that bounded expansion is exactly the condition under which arbitrarily high odd-girth non-bipartite coloring problems are first-order definable on the class. The paper proves the equivalence for hereditary topologically closed classes that are somewhere dense or have bounded expansion, while the general case is conditional on the structural conjecture below.