Rank-Width and Well-Quasi-Ordering

Source abstract

Robertson and Seymour [J. Combin. Theory Ser. B, 48 (1990), pp. 227–254] proved that graphs of bounded tree-width are well-quasi-ordered by the graph minor relation. By extending their arguments, Geelen, Gerards, and Whittle [J. Combin. Theory Ser. B, 84 (2002), pp. 270–290] proved that binary matroids of bounded branch-width are well-quasi-ordered by the matroid minor relation. We prove another theorem of this kind in terms of rank-width and vertex-minors. For a graph $G=(V,E)$ and a vertex v of G, a local complementation at v is an operation that replaces the subgraph induced by the neighbors of v with its complement graph. A graph H is called a vertex-minor of G if H can be obtained from G by applying a sequence of vertex deletions and local complementations. Rank-width was defined by Oum and Seymour [J. Combin. Theory Ser. B, 96 (2006), pp. 514–528] to investigate clique-width; they showed that graphs have bounded rank-width if and only if they have bounded clique-width. We prove that graphs of bounded rank-width are well-quasi-ordered by the vertex-minor relation; in other words, for every infinite sequence $G_1,G_2,\ldots$ of graphs of rank-width (or clique-width) at most k, there exist $i<j$ such that $G_i$ is isomorphic to a vertex-minor of $G_j$. This implies that there is a finite list of graphs such that a graph has rank-width at most k if and only if it contains no one in the list as a vertex-minor. The proof uses the notion of isotropic systems defined by Bouchet.