Paper Info
Title
An Extension of the Blow-up Lemma to Arrangeable Graphs.
Abstract
The blow-up lemma established by Komlos, Sarkozy, and Szemeredi 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 K-s-subdivision for constant s. Our main result shows that a-arrangeable graphs with maximum degree at most root 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 + gamma)n contains an F-factor of every a-arrangeable r-chromatic graph F with at most xi n vertices and maximum degree at most root n/log n, as long as. is sufficiently small compared to gamma/(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 xi n/log n, as long as xi is sufficiently small compared to p/a.
Year
DOI
Venue
2015
10.1137/13093827X
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
Field
DocType
blow-up lemma,regularity lemma,spanning subgraphs,graph embeddings,arrangeable graphs
Discrete mathematics,Combinatorics,Indifference graph,Chordal graph,Degree (graph theory),Cograph,Book embedding,Pathwidth,1-planar graph,Mathematics,Split graph
Journal
Volume
Issue
ISSN
29
2
0895-4801
Citations 
PageRank 
References 
4
0.46
18
Authors
4
Name
Order
Citations
PageRank
Julia Böttcher19317.35
Yoshiharu Kohayakawa247764.87
Anusch Taraz316837.71
Andreas Würfl4253.23