Weisfeiler-Leman stabilisation and the graph isomorphism problem
Presented by Mr. Brendan DOUGLAS
Type: Oral presentation
Track: Association Schemes
The Weisfeiler-Leman (WL) method takes as input an arbitrary graph $\Gamma$, and returns the minimal coherent algebra containing the basis relations of $\Gamma$ (e.g. the set of edges and non-edges). We will discuss some well-known properties of a common higher-dimensional generalisation of this method, the $k$-dim WL method, in particular with respect to its application to the graph isomorphism problem (GI). After describing some properties of the known families of `counterexample' graphs, we will introduce a generalisation to the $k$-dim WL method, involving an initial canonical decomposition of the graph, and discuss properties of potential counterexamples to this extended WL method. The goal of this work is simply to investigate the possibility that a variant of the WL method might be used to solve GI.