Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth

Andreas Krebs, Oleg Verbitsky

Given a connected graph $G$ and its vertex $x$, let $U_x(G)$ denote the universal cover of $G$ obtained by unfolding $G$ into a tree starting from $x$. Let $T=T(n)$ be the minimum…