Verlagslink DOI: 10.1137/13093827X
Titel: An extension of the blow-up lemma to arrangeable graphs
Sprache: Englisch
Autor/Autorin: Böttcher, Julia 
Kohayakawa, Yoshiharu 
Taraz, Anusch 
Würfl, Andreas 
Schlagwörter: Arrangeable graphs; Blow-up lemma; Graph embeddings; Regularity lemma; Spanning subgraphs
Erscheinungs­datum: 4-Jun-2015
Verlag: Soc.
Quellenangabe: SIAM Journal on Discrete Mathematics 29 (2): 962-1001 (2015)
Zusammenfassung (englisch): 
The blow-up lemma established by Komlós, Sárközy, and Szemerédi in 1997 is an important tool for the embedding of spanning subgraphs of bounded maximum degree. Here we prove several generalizations of this result concerning the embedding of a-arrangeable graphs, where a graph is called a-arrangeable if its vertices can be ordered in such a way that the neighbors to the right of any vertex v have at most a neighbors to the left of v in total. Examples of arrangeable graphs include planar graphs and, more generally, graphs without a Ks-subdivision for constant s. Our main result shows that a-arrangeable graphs with maximum degree at most √ n/ log n can be embedded into corresponding systems of superregular pairs. This is optimal up to the logarithmic factor. We also present two applications. We prove that any large enough graph G with minimum degree at least (r-1 r + γ)n contains an F-factor of every a-arrangeable r-chromatic graph F with at most ζn vertices and maximum degree at most √ n/ log n, as long as ζ is sufficiently small compared to γ/(ar). This extends a result of Alon and Yuster [J. Combin. Theory Ser. B, 66 (1996), pp. 269-282]. Moreover, we show that for constant p the random graph G(n, p) is universal for the class of a-arrangeable n-vertex graphs H of maximum degree at most ζn/ log n, as long as ζ is sufficiently small compared to p/a. © 2015 Society for Industrial and Applied Mathematics.
ISSN: 1095-7146
Zeitschrift: SIAM journal on discrete mathematics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige


Letzte Woche
Letzten Monat
checked on 01.10.2022


Letzte Woche
Letzten Monat
checked on 30.06.2022

Google ScholarTM


Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.