Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth

Isolde Adler, Eva Fluck, Tim Seppelt +1

We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment, using homomorphism indistinguishability.…