Excluded vertex-minors for graphs of linear rank-width at most k

Abstract

Linear rank-width is a graph width parameter, which is a variation of rank-width by restricting its tree to a caterpillar. As a corollary of known theorems, for each $k$, there is a finite obstruction set ${\mathcal{O}}_k$ of graphs such that a graph $G$ has linear rank-width at most $k$ if and only if no vertex-minor of $G$ is isomorphic to a graph in ${\mathcal{O}}_k$. However, no attempts have been made to bound the number of graphs in ${\mathcal{O}}_k$ for $k\ge 2$. We show that for each $k$, there are at least $2^{\Omega (3^k)}$ pairwise locally non-equivalent graphs in ${\mathcal{O}}_k$, and therefore the number of graphs in ${\mathcal{O}}_k$ is at least double exponential. To prove this theorem, it is necessary to characterize when two graphs in ${\mathcal{O}}_k$ are locally equivalent. A graph is a block graph if all of its blocks are complete graphs. We prove that if two block graphs without simplicial vertices of degree at least $2$ are locally equivalent, then they are isomorphic. This not only is useful for our theorem but also implies a theorem of Bouchet [Transforming trees by successive local complementations, J. Graph Theory 12 (1988), no. 2, 195-207] stating that if two trees are locally equivalent, then they are isomorphic.

19 pages, 8 figures. An extended abstract appeared in Proc. 30th International Symposium on Theoretical Aspects of Computer Science, 2013 (STACS2013)

Cited by in corpus (6)

• Rank-width: Algorithmic and structural results
• The "art of trellis decoding" is fixed-parameter tractable
• Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
• Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
• Scattered classes of graphs
• Graphs of bounded depth-$2$ rank-brittleness