5 citations · 6 across the 3 of their papers we have counts for
7 papers
Gathering Information about a Graph by Counting Walks from a Single Vertex
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky +1
We say that a vertex in a connected graph is decisive if the numbers of walks from of each length determine the graph rooted at up to isomorphism among all conn…
The Weisfeiler-Leman Algorithm and Recognition of Graph Properties
Frank Fuhlbrück, Johannes Köbler, Ilia Ponomarenko +1
The -dimensional Weisfeiler-Leman algorithm (-WL) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of -WL to recognition of g…
Local WL Invariance and Hidden Shades of Regularity
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
The -dimensional Weisfeiler-Leman algorithm is a powerful tool in graph isomorphism testing. For an input graph , the algorithm determines a canonical coloring of -tuples…
On the Weisfeiler-Leman Dimension of Fractional Packing
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
The -dimensional Weisfeiler-Leman procedure (-WL), which colors -tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely…
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm
Frank Fuhlbrück, Johannes Köbler, Oleg Verbitsky
As it is well known, the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical 2-dimensional Weisfeiler-Leman algorithm (2-WL…
On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
The -dimensional Weisfeiler-Leman algorithm (-WL) is a fruitful approach to the Graph Isomorphism problem. 2-WL corresponds to the original algorithm suggested by Weisfeiler…
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler +2
In this paper we study the complexity of the following problems: Given a colored graph X=(V,E,c), compute a minimum cardinality set S of vertices such that no nontrivial automorphi…