A Lower Bound for the Weisfeiler-Leman Dimension of Circulant Graphs

Abstract

It is proved that for infinitely many positive integers $n$, there exists a circulant graph of order $n$ whose Weisfeiler-Leman dimension is at least $c\sqrt{\log n}$ for some constant $c>0$ not depending on $n$.