Options
Spanning embeddings of arrangeable graphs with sublinear bandwidth
Publikationstyp
Journal Article
Date Issued
2016-03-01
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
48
Issue
2
Start Page
270
End Page
289
Citation
Random Structures and Algorithms 2 (48): 270-289 (2016-03-01)
Publisher DOI
Scopus ID
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