2018/07/26 by Hyde, Joseph, Liu, Hong, Treglown, Andrew
#05C35 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1807.10203
An important result of Komlós [Tiling Turán theorems, Combinatorica, 2000] yields the asymptotically exact minimum degree threshold that ensures a graph G contains an H-tiling covering an xth proportion of the vertices of G (for any fixed x ∈ (0,1) and graph H). We give a degree sequence strengthening of this result which allows for a large proportion of the vertices in the host graph G to have degree substantially smaller than that required by Komlós' theorem. We also demonstrate that for certain graphs H, the degree sequence condition is essentially best possible in more than one sense.