...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >RANK-WIDTH AND WELL-QUASI-ORDERING
【24h】

RANK-WIDTH AND WELL-QUASI-ORDERING

机译：秩和良好排序

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：罗伯逊和西摩[J.组合理论系列B，48（1990），pp。227-254]证明了有界树宽的图是由图的次要关系很好地排序的。通过扩展他们的论点，Geelen，Gerards和Whittle [J.组合理论系列B，84（2002），pp。270-290]证明了有界分支宽度的二元拟阵由拟阵次要关系很好地拟序。我们证明了另一种关于秩宽度和次顶点的定理。对于图G =（V，E）和G的顶点v，在v处的局部补码是用其补图替换v的邻居所诱发的子图的运算。如果可以通过应用一系列顶点删除和局部补全从G中获得H，则图H称为G的顶点次顶点。等级宽度由Oum和Seymour定义[J.组合理论系列B，96（2006），第514-528页]中研究了集团宽度。他们表明，当且仅当图的边界宽度为界时，图的边界宽度才为界。我们证明了有界秩宽度的图是由顶点-次要关系很好拟的；换句话说，对于最多k个秩宽度（或集团宽度）的图的每个无限序列G_1，G_2 ...，存在i

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号