Spanning embeddings of arrangeable graphs with sublinear bandwidth
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
| Item Type | Article |
|---|---|
| Copyright holders | © 2015 Wiley Periodicals, Inc. |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1002/rsa.20593 |
| Date Deposited | 26 Jan 2016 |
| URI | https://researchonline.lse.ac.uk/id/eprint/65152 |
Explore Further
- http://www.lse.ac.uk/Mathematics/people/Julia-Boettcher.aspx (Author)
- https://www.scopus.com/pages/publications/84952987533 (Scopus publication)
- http://onlinelibrary.wiley.com/journal/10.1002/(IS... (Official URL)