DC Field | Value | Language |
---|---|---|
dc.contributor.author | Oum, Sang-il | ko |
dc.date.accessioned | 2008-06-23T05:56:01Z | - |
dc.date.available | 2008-06-23T05:56:01Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 2008 | - |
dc.identifier.citation | SIAM JOURNAL ON DISCRETE MATHEMATICS, v.22, no.2, pp.666 - 682 | - |
dc.identifier.issn | 0895-4801 | - |
dc.identifier.uri | http://hdl.handle.net/10203/5249 | - |
dc.description.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),... 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. | - |
dc.description.sponsorship | This work was performed while the author was at the Pro- gram in Applied and Computational Mathematics, Princeton University, Princeton, New Jersey and partially supported by the SRC program of Korea Science and Engi- neering Foundation grant funded by Korea government (MOST)(No. R11-2007-035- 01002-0). | en |
dc.language | English | - |
dc.language.iso | en_US | en |
dc.publisher | SIAM PUBLICATIONS | - |
dc.subject | VERTEX-MINORS | - |
dc.subject | BRANCH-WIDTH | - |
dc.subject | CLIQUE-WIDTH | - |
dc.subject | GRAPH MINORS | - |
dc.subject | TREE-WIDTH | - |
dc.subject | OBSTRUCTIONS | - |
dc.subject | MATROIDS | - |
dc.title | Rank-width and well-quasi-ordering | - |
dc.type | Article | - |
dc.identifier.wosid | 000256452900015 | - |
dc.identifier.scopusid | 2-s2.0-67649563575 | - |
dc.type.rims | ART | - |
dc.citation.volume | 22 | - |
dc.citation.issue | 2 | - |
dc.citation.beginningpage | 666 | - |
dc.citation.endingpage | 682 | - |
dc.citation.publicationname | SIAM JOURNAL ON DISCRETE MATHEMATICS | - |
dc.identifier.doi | 10.1137/050629616 | - |
dc.embargo.liftdate | 9999-12-31 | - |
dc.embargo.terms | 9999-12-31 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | rank-width | - |
dc.subject.keywordAuthor | clique-width | - |
dc.subject.keywordAuthor | well-quasi-ordering | - |
dc.subject.keywordAuthor | isotropic system | - |
dc.subject.keywordAuthor | local complementation | - |
dc.subject.keywordAuthor | pivoting | - |
dc.subject.keywordAuthor | binary matroid | - |
dc.subject.keywordAuthor | pivot-minor | - |
dc.subject.keywordAuthor | vertex-minor | - |
dc.subject.keywordPlus | VERTEX-MINORS | - |
dc.subject.keywordPlus | BRANCH-WIDTH | - |
dc.subject.keywordPlus | CLIQUE-WIDTH | - |
dc.subject.keywordPlus | GRAPH MINORS | - |
dc.subject.keywordPlus | TREE-WIDTH | - |
dc.subject.keywordPlus | OBSTRUCTIONS | - |
dc.subject.keywordPlus | MATROIDS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.