Rank-width and well-quasi-ordering

Cited 14 time in webofscience Cited 0 time in scopus
  • Hit : 524
  • Download : 722
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
DOI
10.1137/050629616
URI
http://hdl.handle.net/10203/5249
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 14 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0