Publisher DOI: 10.1002/rsa.20593
Title: Spanning embeddings of arrangeable graphs with sublinear bandwidth
Language: English
Authors: Böttcher, Julia 
Taraz, Anusch 
Würfl, Andreas 
Keywords: Arrangeable graphs; Bandwidth theorem; Graph embedding; Ramsey numbersregularity method
Issue Date: 1-Mar-2016
Source: Random Structures and Algorithms 2 (48): 270-289 (2016-03-01)
Abstract (english): 
The Bandwidth Theorem of Böttcher, et al. [Mathematische Annalen 343 (2009), 175-205] gives minimum degree conditions for the containment of spanning graphs H with small bandwidth and bounded maximum degree. We generalise this result to a-arrangeable graphs H with Δ(H)≤n/logn, where n is the number of vertices of H. Our result implies that sufficiently large n-vertex graphs G with minimum degree at least (34+γ)n contain almost all planar graphs on n vertices 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 graphs H have Ramsey number at most 12|H|. We obtain corresponding results for graphs embeddable on different orientable surfaces.
URI: http://hdl.handle.net/11420/5959
ISSN: 1098-2418
Journal: Random structures & algorithms 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

51
Last Week
1
Last month
2
checked on Jul 5, 2022

SCOPUSTM   
Citations

2
Last Week
0
Last month
0
checked on Jun 30, 2022

Google ScholarTM

Check

Add Files to Item

Note about this record

Cite this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.