• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Excluding subdivisions of bounded degree graphs
【24h】

Excluding subdivisions of bounded degree graphs

机译：不包括有界度图的细分

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

摘要

Let H be a fixed graph. What can be said about graphs G that have no subgraph isomorphic to a subdivision of H? Grohe and Marx proved that such graphs G satisfy a certain structure theorem that is not satisfied by graphs that contain a subdivision of a (larger) graph H-1. Dvorak found a clever strengthening-his structure is not satisfied by graphs that contain a subdivision of a graph H-2, where H-2 has "similar embedding properties" as H. Building upon Dvorak's theorem, we prove that said graphs G satisfy a similar structure theorem. Our structure is not satisfied by graphs that contain a subdivision of a graph H-3 that has similar embedding properties as H and has the same maximum degree as H. This will be important in a forthcoming application to well-quasi-ordering. (C) 2018 Elsevier Inc. All rights reserved.
机译：让H成为一个固定的图表。 关于图表G的图表G可以对H的细分来说是什么？ GROHE和MARX证明，这种图表G满足了不满足于包含（较大）图H-1的细分的图表不满足的特定结构定理。 Dvorak发现了一个聪明的加强 - 他的结构不满足图形H-2的细分的图表，其中H-2具有“类似的嵌入属性”，如同Dvorak的定理，我们证明了所述图表G满足A 类似的结构定理。 我们的结构不满足图表H-3的细分的图表，其具有与H类似的嵌入属性并且具有与H相同的最大程度。这将在即将到来的应用到良好的准订购中是重要的。 （c）2018年Elsevier Inc.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号