Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm

Moritz Lichter, Ilia Ponomarenko, Pascal Schweitzer

We show that the 2-dimensional Weisfeiler-Leman algorithm stabilizes n-vertex graphs after at most O(n log n) iterations. This implies that if such graphs are distinguishable in 3-…