We study the expressive power of first-order logic with counting quantifiers, especially the k-variable and quantifier-rank-q fragment Cᵏq, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~ (2021) proved that two graphs satisfy the same Cᵏq-sentences if and only if they are homomorphism indistinguishable over the class Tᵏq of graphs admitting a k-pebble forest cover of depth q. After reproving this result using elementary means, we provide a graph-theoretic analysis of the graph class Tᵏq. This allows us to separate Tᵏq from the intersection TW₊-₁ TDq, provided that q is sufficiently larger than k. Here TW₊-₁ is the class of all graphs of treewidth at most k-1 and TDq is the class of all graphs of treedepth at most q. We are able to lift this separation to a (semantic) separation of the respective homomorphism indistinguishability relations ₓ㵮ₐ and ₓₖ_₊-₁ TDq. We do this by showing that the classes TDq and Tᵏq are homomorphism distinguishing closed, as conjectured by Roberson~ (2022). In order to prove Roberson's conjecture for Tᵏq we characterise Tᵏq in terms of a monotone Cops-and-Robber game. The crux is to prove that if Cop has a winning strategy then Cop also has a winning strategy that is monotone. To that end, we show how to transform Cops' winning strategy into a pree-tree-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first `cleaning up' procedure along the pree-tree-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of rounds simultaneously across all branches of the decomposition via a vertex exchange argument.
Adler et al. (Fri,) studied this question.