Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic

Sandra Kiefer, Pascal Schweitzer

We show that on graphs with n vertices, the 2-dimensional Weisfeiler-Leman algorithm requires at most O(n^2/log(n)) iterations to reach stabilization. This in particular shows that…