Canonisation and Definability for Graphs of Bounded Rank Width
Canonisation and Definability for Graphs of Bounded Rank Width
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 a graph invariant that, similarly to tree width, measures the width of a certain style of hierarchical decomposition of graphs; …