H-factors in dense graphs

Noga Alon, Raphael Yuster

Research output: Contribution to journalArticlepeer-review

93 Scopus citations

Abstract

The following asymptotic result is proved. For every ε > 0, and for every positive integer h, there exists an n0 = n0(ε, h) such that for every graph H with h vertices and for every n>n0, any graph G with hn vertices and with minimum degree d≥((x(H) - 1)/x(H) +ε) hn contains n vertex disjoint copies of H. This result is asymptotically tight and its proof supplies a polynomial time algorithm for the corresponding algorithmic problem.

Original languageEnglish (US)
Pages (from-to)269-282
Number of pages14
JournalJournal of Combinatorial Theory. Series B
Volume66
Issue number2
DOIs
StatePublished - Mar 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'H-factors in dense graphs'. Together they form a unique fingerprint.

Cite this