Every k-tangle in a graph is the lift of a k-tangle in a topological minor of size bounded by a function of k, reducing the vertex-set induction problem to bounded-size graphs.
Isomorphism Testing for Graphs of Bounded Rank Width
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the clique width of a graph is bounded in terms of its rank width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.
fields
math.CO 1years
2024 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On vertex sets inducing tangles
Every k-tangle in a graph is the lift of a k-tangle in a topological minor of size bounded by a function of k, reducing the vertex-set induction problem to bounded-size graphs.