Spanning embeddings of arrangeable graphs with sublinear bandwidth
Spanning embeddings of arrangeable graphs with sublinear bandwidth
复制标题
具有次线性带宽的可排列图的跨越嵌入
DOI：
10.1002/rsa.20593
复制
发表时间：
2015
影响因子：
1
通讯作者：
A. Würfl
中科院分区：
文献类型：
--
作者：
J. Böttcher;A. Taraz;A. Würfl
Böttcher 等人的带宽定理。 [Mathematische Annalen 343 (2009), 175–205] 给出了包含小带宽和有界最大度的生成图 H 的最小度条件。我们将这个结果推广到可排列图H，其中H的顶点数。我们的结果意味着具有最小度的足够大的顶点图G至少包含n个顶点上的几乎所有平面图作为子图。使用 Allen 等人开发的技术。 [Combinatorica 33 (2013), 125–160] 我们还可以应用我们的方法来证明几乎所有平面图最多具有拉姆齐数 。我们获得了可嵌入不同可定向表面上的图的相应结果。 © 2015 Wiley periodicals, Inc. 随机结构。阿尔格., 48, 270–289, 2016
The Bandwidth Theorem of Böttcher, et al. [Mathematische Annalen 343 (2009), 175–205] gives minimum degree conditions for the containment of spanning graphsHwith small bandwidth and bounded maximum degree. We generalise this result toa‐arrangeable graphsHwith , wherenis the number of vertices ofH.Our result implies that sufficiently largen‐vertex graphsGwith minimum degree at least contain almost all planar graphs onnvertices as subgraphs. Using techniques developed by Allen, et al. [Combinatorica 33 (2013), 125–160] we can also apply our methods to show that almost all planar graphsHhave Ramsey number at most . We obtain corresponding results for graphs embeddable on different orientable surfaces. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 270–289, 2016
登录
查看更多内容
可安排性和集团细分
DOI：
--
发表时间：
2013
期刊：
The Mathematics of Paul Erdős II
影响因子：
--
作者：
V. Rödl;R. Thomas
通讯作者：
R. Thomas
ε-正则图中的完美匹配和爆炸引理
影响因子：
1.1
作者：
V. Rödl;A. Rucinski
通讯作者：
A. Rucinski
DOI：
10.1137/13093827x
发表时间：
--
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
J. Böttcher;Y. Kohayakawa;A. Taraz;A. Würfl
通讯作者：
A. Würfl
Bollobás 和 Komlós 带宽猜想的证明
影响因子：
1.4
作者：
Julia Böttcher;M. Schacht;A. Taraz
通讯作者：
A. Taraz
DOI：
--
发表时间：
1996
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
J. Komlos;G. N. Sárközy;E. Szemerédi
通讯作者：
E. Szemerédi