We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~(2021) proved that two graphs satisfy the same $k$-variable and quantifier-rank-$q$ sentences if and only if they are homomorphism indistinguishable over the class 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 this graph class. This allows us to separate it from the intersection of the class of all graphs of treewidth at most $k-1$ and the class of all graphs of treedepth at most $q$, provided that $q$ is sufficiently larger than $k$. We are able to lift this separation to a (semantic) separation of the respective homomorphism indistinguishability relations. We do this by showing that the graph classes of all graphs of treedepth at most $q$ and of graphs admitting a $k$-pebble forest cover of depth $q$ are homomorphism distinguishing closed, as conjectured by Roberson~(2022). In order to prove Roberson's conjecture for the class of graphs admitting a $k$-pebble forest cover of depth $q$ we characterise the class 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 Cop's winning strategy into a pre-tree-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first `cleaning up' procedure along the pre-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. arXiv admin note: text overlap with arXiv:2308.06044

We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment $\mathsf{C}^k_q$, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio (2021) proved that two graphs satisfy the same $\mathsf{C}^k_q$-sentences if and only if they are homomorphism indistinguishable over the class $\mathcal{T}^k_q$ of graphs admitting a $k$-pebble forest cover of depth $q$. Their proof builds on the categorical framework of game comonads developed by Abramsky, Dawar, and Wang (2017). We reprove their result using elementary techniques inspired by Dvořák (2010). Using these techniques we also give a characterisation of guarded counting logic. Our main focus, however, is to provide a graph theoretic analysis of the graph class $\mathcal{T}^k_q$. This allows us to separate $\mathcal{T}^k_q$ from the intersection of the graph class $\mathcal{TW}_{k-1}$, that is graphs of treewidth less or equal $k-1$, and $\mathcal{TD}_q$, that is graphs of treedepth at most $q$ if $q$ is sufficiently larger than $k$. We are able to lift this separation to the semantic separation of the respective homomorphism indistinguishability relations. A part of this separation is to prove that the class $\mathcal{TD}_q$ is homomorphism distinguishing closed, which was already conjectured by Roberson (2022).