On the decomposition threshold of a given graph
On the decomposition threshold of a given graph
复制标题
关于给定图的分解阈值
DOI：
10.1016/j.jctb.2019.02.010
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Glock S
中科院分区：
文献类型：
--
作者：
Glock S
我们研究给定图 F 的 F 分解阈值 δ F。这里图 G 的 F 分解是 G 中 F 的边不相交副本的集合，它们一起覆盖 G 的每条边。（这样的 F 分解仅在 G 是 F 可整除的情况下才存在，即如果 e (F)| e (G) 且 G 的每个顶点度可以表示为 F 的顶点度的线性组合。） F 分解阈值 δ F 是确保 δ (G)≥(δ F+ o (1)) n 的 n 个顶点上的 F 整除图 G 具有 F 分解的最小值。对于给定的图 F，我们的主要结果意味着以下结果，其中 δ F⁎ 是 δ F 和 χ:= χ (F):(i) δ F≤ max{δ F⁎, 1− 1/(χ+ 1)};(ii) 如果 χ≥ 5，则 δ F∈{δ F⁎, 1− 1/χ, 1− 1/(χ+ 1)};(iii) 我们确定 δ F 如果 F 是二分的。特别是，(i) 意味着 δ K r= δ K r⁎。我们的证明涉及最近“迭代”吸收方法的进一步发展。
We study the F-decomposition threshold δ F for a given graph F. Here an F-decomposition of a graph G is a collection of edge-disjoint copies of F in G which together cover every edge of G.(Such an F-decomposition can only exist if G is F-divisible, ie if e (F)| e (G) and each vertex degree of G can be expressed as a linear combination of the vertex degrees of F.) The F-decomposition threshold δ F is the smallest value ensuring that an F-divisible graph G on n vertices with δ (G)≥(δ F+ o (1)) n has an F-decomposition. Our main results imply the following for a given graph F, where δ F⁎ is the fractional version of δ F and χ:= χ (F):(i) δ F≤ max{δ F⁎, 1− 1/(χ+ 1)};(ii) if χ≥ 5, then δ F∈{δ F⁎, 1− 1/χ, 1− 1/(χ+ 1)};(iii) we determine δ F if F is bipartite. In particular,(i) implies that δ K r= δ K r⁎. Our proof involves further developments of the recent ‘iterative’absorbing approach.
登录
查看更多内容
DOI：
10.1017/s0963548317000165
发表时间：
2016
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
R. Montgomery
通讯作者：
R. Montgomery
k 色图的 H 堆积
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
R. Yuster
通讯作者：
R. Yuster
DOI：
--
发表时间：
2017
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
R. Montgomery
通讯作者：
R. Montgomery
DOI：
10.1016/j.jctb.2017.05.005
发表时间：
2017
期刊：
Journal of Combinatorial Theory, Series B
影响因子：
--
作者：
Barber B
通讯作者：
Barber B
DOI：
10.1016/j.jcta.2017.04.005
发表时间：
2017
期刊：
Journal of Combinatorial Theory, Series A
影响因子：
--
作者：
Barber B
通讯作者：
Barber B