Generalizations of $k$-Weisfeiler-Leman partitions and related graph invariants

Anuj Dawar, Danny Vagnozzi

The family of Weisfeiler-Leman equivalences on graphs is a widely studied approximation of graph isomorphism with many different characterizations. We give a generalization of these by adding a width parameter $r$ and show that these can be linked to a lifting of the classical Weisfeiler-Leman equivalence defined by Evdokimov and Ponomarenko and a $k$-boson invariant introduced in the context of quantum random walks. We also prove a characterization in terms of an invertible map game (as introduced by Dawar-Holm) on the complex field, which introduces new parameters that allow us to tease apart some subtle variations of the usual Weisfeiler-Leman equivalences.

Knowledge Graph



Sign up or login to leave a comment