A bandwidth theorem for approximate decompositions
A bandwidth theorem for approximate decompositions
复制标题
近似分解的带宽定理
DOI：
10.1112/plms.12218
复制
发表时间：
2018
影响因子：
1.8
通讯作者：
Condon P
中科院分区：
文献类型：
--
作者：
Condon P
我们在正则顶点图上给出了一个度条件，该条件保证了任何有界度顶点色可分图族的近最优填充的存在性。一般来说，这个度条件是最好的。这里一个图是可分的，如果它有一个次线性分隔符，去除它会产生一组次线性大小的分量。等价地，可分性条件可以用具有小带宽的条件来代替。因此，我们的结果可以看作是Böttcher，Schacht和Taraz的带宽定理在近似分解下的一个版本。更准确地说，设是所有的下确界，确保任何足够大的正则顶点图的近似分解至少是度。现在假设这是一个顶点图，它对于某些图是接近正则的，并且假设这是一个有界度顶点色可分图序列，其中。我们证明了存在一个边不交的填充，如果它们是二分的，则有充分条件。特别是，这产生了一个近似版本的树包装猜想的设置定期hostgraphsof高度。同样，我们的结果意味着近似版本的Oberwolfach问题，Alspach问题和存在的可解设计的设置定期主机图的高度。
We provide a degree condition on a regular‐vertex graphwhich ensures the existence of a near optimal packing of any familyof bounded degree‐vertex‐chromatic separable graphs into. In general, this degree condition is best possible.Here a graph is separable if it has a sublinear separator whose removal results in a set of components of sublinear size. Equivalently, the separability condition can be replaced by that of having small bandwidth. Thus our result can be viewed as a version of the bandwidth theorem of Böttcher, Schacht and Taraz in the setting of approximate decompositions.More precisely, letbe the infimum over allensuring an approximate‐decomposition of any sufficiently large regular‐vertex graphof degree at least. Now suppose thatis an‐vertex graph which is close to‐regular for someand suppose thatis a sequence of bounded degree‐vertex‐chromatic separable graphs with. We show that there is an edge‐disjoint packing ofinto.If theare bipartite, thenis sufficient. In particular, this yields an approximate version of the tree packing conjecture in the setting of regular host graphsof high degree. Similarly, our result implies approximate versions of the Oberwolfach problem, the Alspach problem and the existence of resolvable designs in the setting of regular host graphs of high degree.
登录
查看更多内容
影响因子：
1.7
作者：
Allen P
通讯作者：
Allen P
无限阶集合的 Oberwolfach 问题的完整解决方案
DOI：
--
发表时间：
2009
期刊：
J. Comb. Theory B
影响因子：
--
作者：
D. Bryant;Victor Scharaschkin
通讯作者：
Victor Scharaschkin
DOI：
--
发表时间：
2017
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
R. Montgomery
通讯作者：
R. Montgomery
可解析图设计的渐近存在性
DOI：
--
发表时间：
2007
期刊：
Canadian mathematical bulletin
影响因子：
--
作者：
P. Dukes;A. Ling
通讯作者：
A. Ling
关于 Bollobás、Eldridge 和 Catlin 的图包装猜想
DOI：
--
发表时间：
2008
期刊：
Comb.
影响因子：
--
作者：
Hemanshu Kaul;A. Kostochka;Gexin Yu
通讯作者：
Gexin Yu