Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them

Snir Hordan, Nadav Dym, Tim Seppelt

Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number $k$, the $k$-Weisfeiler-Leman ($k$-WL) test cannot distinguish all no…