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),... 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.

- Publisher
- SIAM PUBLICATIONS

- Issue Date
- 2008

- Language
- English

- Article Type
- Article

- Keywords
VERTEX-MINORS; BRANCH-WIDTH; CLIQUE-WIDTH; GRAPH MINORS; TREE-WIDTH; OBSTRUCTIONS; MATROIDS

- Citation
SIAM JOURNAL ON DISCRETE MATHEMATICS, v.22, no.2, pp.666 - 682

- ISSN
- 0895-4801

- Appears in Collection
- MA-Journal Papers(저널논문)

- Files in This Item

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.