Title: The 3-dim Weisfeiler-Leman algorithm tests isomorphism of planar graphs
One of ingredients of Babai's quasipolynomial graph isomorphism test is the $m$-dimensional Weisfeiler-Leman algorithm (m-dim WL). In the present talk, we describe this algorithm explicitly as a procedure to construct a stable coloring of the m-tuples (the ordinary WL algorithm corresponds to the case m=2). It will be explained why for m ge 3, the m-dim WL tests isomorphism of any pair of planar graphs correctly (the previous known bound was mge 14).
An easy example shows that the 1-dim WL does not recognize isomorphism of planar graphs.
The question, whether m=2 is enough, remains open.
This talk is based on a joint paper with Sandra Kiefer and Pascal Schweitzer.