...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Combinatorial Theory, Series B >Induced subgraphs of graphs with large chromatic number. VI. Banana trees
【24h】

Induced subgraphs of graphs with large chromatic number. VI. Banana trees

机译：诱导具有大色数的图表的子图。 VI。 香蕉树

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

摘要

We investigate which graphs H have the property that in every graph with bounded clique number and sufficiently large chromatic number, some induced subgraph is isomorphic to a subdivision of H. In an earlier paper [6], the first author proved that every tree has this property; and in another earlier paper with Maria Chudnovsky [2], we proved that every cycle has this property. Here we give a common generalization. Say a "banana" is the union of a set of paths all with the same ends but otherwise disjoint. We prove that if H is obtained from a tree by replacing each edge by a banana then H has the property mentioned. (C) 2020 Elsevier Inc. All rights reserved.
机译：我们研究了哪些图H具有这样的性质：在每一个具有有界团数和足够大色数的图中，某些诱导子图同构于H的一个子图。在之前的文章[6]中，第一作者证明了每一棵树都具有这个性质；在Maria Chudnovsky[2]的另一篇早期论文中，我们证明了每个循环都有这个性质。这里我们给出一个通用的概括。假设“香蕉”是一组路径的并集，所有路径都有相同的端点，但在其他方面是不相交的。我们证明，如果H是通过用香蕉代替每一条边从树上得到的，则H具有上述性质。（C） 2020爱思唯尔公司版权所有。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号