A degree sequence Komlós theorem

Joseph Hyde, Hong Liu, Andrew Treglown

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
204 Downloads (Pure)

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 languageEnglish
Pages (from-to)2041-2061
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number4
DOIs
Publication statusPublished - 22 Oct 2019

Keywords

  • Degree sequence
  • Graph tilings
  • Regularity method

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'A degree sequence Komlós theorem'. Together they form a unique fingerprint.

Cite this