Spanning embeddings of arrangeable graphs with sublinear bandwidth

Böttcher, J.ORCID logo, Taraz, A. & Würfl, A. (2015). Spanning embeddings of arrangeable graphs with sublinear bandwidth. Random Structures and Algorithms, 48(2), 270-289. https://doi.org/10.1002/rsa.20593
Copy

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 inline image, where n is the number of vertices of H. Our result implies that sufficiently large n-vertex graphs G with minimum degree at least inline image 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 inline image. We obtain corresponding results for graphs embeddable on different orientable surfaces

picture_as_pdf

subject
Accepted Version

Download

Export as

EndNote BibTeX Reference Manager Refer Atom Dublin Core JSON Multiline CSV
Export