Proof of the Alon-Yuster conjecture

János Komlós, Gábor N. Sárközy, Endre Szemerédi

Research output: Contribution to journalArticlepeer-review

73 Scopus citations

Abstract

In this paper we prove the following conjecture of Alon and Yuster. Let H be a graph with h vertices and chromatic number k. There exist constants c(H) and n0(H) such that if n ≥ n0(H) and G is a graph with hn vertices and minimum degree at least (1 - 1/k)hn + c(H), then G contains an H-factor. In fact, we show that if H has a k-coloring with color-class sizes h1 ≤ h2 ≤ ⋯ ≤ hk, then the conjecture is true with c(H)=hk+hk-1 - 1.

Original languageEnglish (US)
Pages (from-to)255-269
Number of pages15
JournalDiscrete Mathematics
Volume235
Issue number1-3
DOIs
StatePublished - May 28 2001

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Proof of the Alon-Yuster conjecture'. Together they form a unique fingerprint.

Cite this