Canonisation and Definability for Graphs of Bounded Rank Width

Martin Grohe, Daniel Neuen

We prove that the combinatorial Weisfeiler-Leman algorithm of dimension $(3k+4)$ is a complete isomorphism test for the class of all graphs of rank width at most $k$. Rank width is…