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\v{ r}\'ak (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).
Categories: cs.LO cs.DM