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

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 kk, there is a finite obstruction set OkOk of graphs such that a graph GG has linear rank-width at most kk if and only if no vertex-minor of GG is isomorphic to a graph in OkOk. However, no attempts have been made to bound the number of graphs in OkOk for k≥2k≥2. We show that for each kk, there are at least 2Ω(3k)2Ω(3k) pairwise locally non-equivalent graphs in OkOk, and therefore the number of graphs in OkOk is at least double exponential.To prove this theorem, it is necessary to characterize when two graphs in OkOk 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 22 are locally equivalent, then they are isomorphic. This not only is useful for our theorem but also implies a theorem of Bouchet (1988) stating that if two trees are locally equivalent, then they are isomorphic.