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 (3 k +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 …