Ilya Ponomarenko (Petersburg Department of V. A. Steklov Institute of Mathematics, Russia)

Title: The 3-dim Weisfeiler-Leman algorithm tests isomorphism of planar graphs

Abstract:

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.