Computational complexity of the Weisfeiler-Leman dimension

Moritz Lichter, Simon Raßmann, Pascal Schweitzer

The Weisfeiler-Leman dimension of a graph $G$ is the least number $k$ such that the $k$-dimensional Weisfeiler-Leman algorithm distinguishes $G$ from every other non-isomorphic gra…