Spanning embeddings of arrangeable graphs with sublinear bandwidth

Publikationstyp
Journal Article
Date Issued
2016-03-01
Sprache
English
Author(s)
Böttcher, Julia  
Taraz, Anusch  
Würfl, Andreas  
Institut
Mathematik E-10  
TORE-URI
http://hdl.handle.net/11420/5959
Journal
Random structures & algorithms  
Volume
48
Issue
2
Start Page
270
End Page
289
Citation
Random Structures and Algorithms 2 (48): 270-289 (2016-03-01)
Publisher DOI
10.1002/rsa.20593
Scopus ID
2-s2.0-84952987533
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.
Subjects
Arrangeable graphs
Bandwidth theorem
Graph embedding
Ramsey numbersregularity method