Abstract
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 $x$th proportion of the vertices of $G$ (for any fixed $x \in (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's theorem. We also demonstrate that for certain graphs $H$, the degree sequence condition is essentially best possible in more than one sense.
| Original language | English |
|---|---|
| Pages (from-to) | 2041-2061 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 33 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 22 Oct 2019 |
Keywords
- Degree sequence
- Graph tilings
- Regularity method
ASJC Scopus subject areas
- General Mathematics
Fingerprint
Dive into the research topics of 'A degree sequence Komlós theorem'. Together they form a unique fingerprint.Projects
- 1 Finished
-
EPSRC Fellowship: Dr Andrew Treglown - Independence in groups, graphs and the integers
Treglown, A. (Principal Investigator)
Engineering & Physical Science Research Council
1/06/15 → 31/05/18
Project: Research Councils
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver