Triangle factors of graphs without large independent sets and of weighted graphs
Triangle factors of graphs without large independent sets and of weighted graphs
复制标题
无大独立集的图和加权图的三角因子
DOI：
10.1002/rsa.20670
复制
发表时间：
2016
影响因子：
1
通讯作者：
M. Sharifzadeh
中科院分区：
文献类型：
--
作者：
J. Balogh;T. Molla;M. Sharifzadeh
经典的Corrádi-Hajnal定理证明了：当δ（G）≥2n/3时，每个n-顶点图G都含有一个三角因子，当3| n .在本文中，我们提出了两个相关的结果，都使用吸收技术的Rödl，Rucibrski和Szemerédi。我们的主要结果确定了保证具有次线性独立数的图的三角形因子所需的最小度条件。特别地，我们证明了如果G是一个n-顶点图，α（G）=o（n）且δ（G）≥（1/2+o（1））n，则G有一个三角因子，并且这是渐近最佳可能的.进一步证明了对每个r，如果图G的每个线性大小点集都有二次边，且δ（G）≥（1/2+o（1））n，则G对n有一个充分大的Kr-因子。我们还提出了许多相关的开放问题，其解决方案可以显示与Ramsey-Turán理论的关系。
The classical Corrádi‐Hajnal theorem claims that every n‐vertex graph G with δ(G)≥2n/3 contains a triangle factor, when 3|n . In this paper we present two related results that both use the absorbing technique of Rödl, Ruciński and Szemerédi. Our main result determines the minimum degree condition necessary to guarantee a triangle factor in graphs with sublinear independence number. In particular, we show that if G is an n‐vertex graph with α(G)=o(n) and δ(G)≥(1/2+o(1))n , then G has a triangle factor and this is asymptotically best possible. Furthermore, it is shown for every r that if every linear size vertex set of a graph G spans quadratically many edges, and δ(G)≥(1/2+o(1))n , then G has a Kr‐factor for n sufficiently large. We also propose many related open problems whose solutions could show a relationship with Ramsey‐Turán theory.
没有大型独立集的图中的三角形平铺
DOI：
10.1017/s0963548318000196
发表时间：
2018
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
BALOGH J
通讯作者：
BALOGH J
影响因子：
1.1
作者：
D. Kühn;Deryk Osthus
通讯作者：
D. Kühn;Deryk Osthus