The Iteration Number of the Weisfeiler-Leman Algorithm

Martin Grohe, Moritz Lichter, Daniel Neuen

We prove new upper and lower bounds on the number of iterations the $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) requires until stabilization. For $k\ge 3$, we show that $…