8 citations · 8 across the 1 of their papers we have counts for
4 papers · 1 filter
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs
Martin Grohe, Sandra Kiefer
The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial procedure for detecting symmetries in graphs and it is widely used in graph-isomorphism tests. It proceeds by iter…
The Iteration Number of Colour Refinement
Sandra Kiefer, Brendan D. McKay
The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem.…
A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus
Martin Grohe, Sandra Kiefer
The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inherent descriptive complexity of the graph. While originally derived from a combinatorial graph isomorphism te…
The Weisfeiler-Leman Dimension of Planar Graphs is at most 3
Sandra Kiefer, Ilia Ponomarenko, Pascal Schweitzer
We prove that the Weisfeiler-Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in first-order logic…