Verlagslink DOI: 10.1002/rsa.20593
Titel: Spanning embeddings of arrangeable graphs with sublinear bandwidth
Sprache: Englisch
Autor/Autorin: Böttcher, Julia 
Taraz, Anusch 
Würfl, Andreas 
Schlagwörter: Arrangeable graphs; Bandwidth theorem; Graph embedding; Ramsey numbersregularity method
Erscheinungs­datum: 1-Mär-2016
Quellenangabe: Random Structures and Algorithms 2 (48): 270-289 (2016-03-01)
Zusammenfassung (englisch): 
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
Zeitschrift: Random structures & algorithms 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

61
Letzte Woche
1
Letzten Monat
2
checked on 04.10.2022

SCOPUSTM   
Zitate

2
Letzte Woche
0
Letzten Monat
0
checked on 30.06.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.