Refining the graph density condition for the existence of almost K-factors

Noga Alon, Eldar Fischer

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

Alon and Yuster [4] have proven that if a fixed graph K on g vertices is (h + 1)-colorable, then any graph G with n vertices and minimum degree at least h/h+1n contains at least (1 - ∈)n/g vertex disjoint copies of K, provided n > N(∈). It is shown here that the required minimum degree of G for this result to follow is closer to h-1/hn, provided K has a proper (h + 1)-coloring in which some of the colors occur rarely. A conjecture regarding the best possible result of this type is suggested.

Original languageEnglish (US)
Pages (from-to)296-308
Number of pages13
JournalArs Combinatoria
Volume52
StatePublished - Jun 1 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Refining the graph density condition for the existence of almost K-factors'. Together they form a unique fingerprint.

Cite this