...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >AN EXTENSION OF THE BLOW-UP LEMMA TO ARRANGEABLE GRAPHS
【24h】

AN EXTENSION OF THE BLOW-UP LEMMA TO ARRANGEABLE GRAPHS

机译：爆破引理扩展到可配置的图

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

摘要

The blow-up lemma established by Komlos, Sarkozy, and Szemeredi in 1997 is an important tool for the embedding of spanning subgraphs of bounded maximum degree. Here we prove several generalizations of this result concerning the embedding of a-arrangeable graphs, where a graph is called a-arrangeable if its vertices can be ordered in such a way that the neighbors to the right of any vertex v have at most a neighbors to the left of v in total. Examples of arrangeable graphs include planar graphs and, more generally, graphs without a K-s-subdivision for constant s. Our main result shows that a-arrangeable graphs with maximum degree at most root n/log n can be embedded into corresponding systems of superregular pairs. This is optimal up to the logarithmic factor. We also present two applications. We prove that any large enough graph G with minimum degree at least (r-1/r + gamma)n contains an F-factor of every a-arrangeable r-chromatic graph F with at most xi n vertices and maximum degree at most root n/log n, as long as. is sufficiently small compared to gamma/(ar). This extends a result of Alon and Yuster [J. Combin. Theory Ser. B, 66 (1996), pp. 269-282]. Moreover, we show that for constant p the random graph G(n, p) is universal for the class of a-arrangeable n-vertex graphs H of maximum degree at most xi n/log n, as long as xi is sufficiently small compared to p/a.
机译：由Komlos，Sarkozy和Szemeredi在1997年建立的爆炸引理是嵌入有界最大度数的跨子图的重要工具。在这里，我们证明该结果与嵌入a-可布置图有关的几种概括，其中一个图的顶点可以按某种方式排序，即任何顶点v右侧的邻居至多具有一个邻居，则该图被称为a-可布置总共位于v的左侧。可布置图的例子包括平面图，并且更一般地，图包括没有针对常数s的K-s细分的图。我们的主要结果表明，最多可将根n / log n的最大程度的a可布置图嵌入到超规则对的相应系统中。这是对数因子的最佳选择。我们还介绍了两个应用程序。我们证明任何最小度至少为（r-1 / r +γn）n的足够大的图G都包含每个具有a个可排列的r色图F的F因子，该图最多具有xi个顶点，并且具有最大的根数n / log n，只要。与γ/（ar）相比足够小。这扩展了Alon和Yuster的结果[J.组合理论系列B，66（1996），第269-282页]。此外，我们表明，对于常数p，只要xi足够小，则随机图G（n，p）对于最大度为xi n / log n的一类可布置n-顶点图H都是通用的至p / a。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号