Going Deep and Going Wide: Counting Logic and Homomorphism Indistinguishability over Graphs of Bounded Treedepth and Treewidth

Eva Fluck, Tim Seppelt, Gian Luca Spitzer

We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment ${\mathsf{C}}_q^k$, using homomorphism indi…