On the Weisfeiler–Leman dimension of circulant graphs

Циркулянтным графом называется любой граф Кэли над конечной циклической группой. Под размерностью Вейсфейлера-Лемана циркулянтного графа $X$ относительно класса всех циркулянтных графов понимается наименьшее положительное целое число $m$, такое что $m$-мерный алгоритм Вейсфейлера-Лемана корректно проверяет изоморфизм между $X$ и любым другим циркулянтным графом. Доказано, что для циркулянтного графа порядка $n$ эта размерность меньше или равна $\Omega(n)+3$, где $\Omega(n)$ – общее число простых делителей числа $n$.