5 citations · 17 across the 10 of their papers we have counts for
15 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…
On the Expressibility of the Reconstructional Color Refinement
V. Arvind, Johannes Köbler, Oleg Verbitsky
One of the most basic facts related to the famous Ulam reconstruction conjecture is that the connectedness of a graph can be determined by the deck of its vertex-deleted subgraphs,…
On a Hierarchy of Spectral Invariants for Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler +1
We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard…
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…
Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable
V. Arvind, Johannes Köbler, Sebastian Kuhnert +1
Lubiw showed that several variants of Graph Isomorphism are NP-complete, where the solutions are required to satisfy certain additional constraints [SICOMP 10, 1981]. One of these,…
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…
Graph Isomorphism, Color Refinement, and Compactness
V. Arvind, Johannes Köbler, Gaurav Rattan +1
Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a…
On the Isomorphism Problem for Helly Circular-Arc Graphs
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the…
Circular-arc hypergraphs: Rigidity via Connectedness
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
A circular-arc hypergraph is a hypergraph admitting an arc ordering, that is, a circular ordering of the vertex set such that every hyperedge is an arc of consecutive ve…
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky
We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where `canonical' means that models of isomorphic graphs are e…
From Invariants to Canonization in Parallel
Johannes Koebler, Oleg Verbitsky
A function of a graph is called a complete graph invariant if the isomorphism of graphs and is equivalent to the equality . If, in addition, is a grap…