Fractional Triangle Decompositions in Graphs with Large Minimum Degree
Fractional Triangle Decompositions in Graphs with Large Minimum Degree
复制标题
具有大最小度的图中的分数三角形分解
DOI：
10.1137/15m1014310
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
François Dross
中科院分区：
文献类型：
--
作者：
François Dross
图的三角形分解是将它的边划分成三角形。图的分式三角形分解是指将非负权赋给图中的每个三角形，使得包含任何给定边的三角形的权之和为1。证明了$n$顶点上的最小度至少为$0.9n$的图都有分数三角分解。这改进了Garaschuk的一个结果，即对于最小度至少为$0.956n$的图，同样的结论也适用。结合Barber，Kuhn，Lo和Osdars最近的一个结果，这意味着对于所有$\epsilon>；0$，在$n$顶点上的每个足够大的最小度至少为$(0.9+\epsilon)n$的三角形可分图都允许三角形分解。
A triangle decomposition of a graph is a partition of its edges into triangles. A fractional triangle decomposition of a graph is an assignment of a nonnegative weight to each of its triangles such that the sum of the weights of the triangles containing any given edge is one. We prove that every graph on $n$ vertices with minimum degree at least $0.9n$ has a fractional triangle decomposition. This improves a result of Garaschuk that the same conclusion holds for graphs with minimum degree at least $0.956n$. Together with a recent result of Barber, Kuhn, Lo, and Osthus, this implies that for all $\epsilon > 0$, every large enough triangle divisible graph on $n$ vertices with minimum degree at least $(0.9 + \epsilon)n$ admits a triangle decomposition.
DOI：
10.1016/j.jctb.2017.05.005
发表时间：
2017
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
Barber B
通讯作者：
Barber B