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

摘要

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 set Ok 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 O_k. However, no attempts have been made to bound the number of graphs in Ok for k > 2. We construct, for each k, 2~(?(3~k)) pairwise locally non-equivalent graphs that are excluded vertex-minors for graphs of linear rank-width at most k. Therefore the number of graphs in O_k is at least double exponential.