Generalizations of k-Weisfeiler-Leman partitions and related graph invariants
share
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.
READ FULL TEXT