• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >REFINING A TREE-DECOMPOSITION WHICH DISTINGUISHES TANGLES
【24h】

REFINING A TREE-DECOMPOSITION WHICH DISTINGUISHES TANGLES

机译：完善区分树的分解

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

摘要

Roberston and Seymour introduced tangles of order k as objects representing highly connected parts of a graph and showed that every graph admits a tree-decomposition of adhesion < k in which each tangle of order k is contained in a different part. Recently, Carmesin, Diestel, Hamann, and Hundertmark showed that such a tree-decomposition can be constructed in a canonical way, which makes it invariant under automorphisms of the graph. These canonical tree-decompositions necessarily have parts which contain no tangle of order k, which we call inessential. Diestel asked what could be said about the structure of the inessential parts. In this paper we show that the torsos of the inessential parts in these tree-decompositions have branch-width < k, allowing us to further refine the canonical tree-decompositions and also show that a similar result holds for k-blocks. We also use our methods to further re fine the essential parts in such a tree-decomposition in a similar fashion.
机译：Roberston和Seymour引入了k阶缠结作为表示图的高度连接部分的对象，并表明每个图都允许树的附着力分解

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号