Towards a weighted version of the hajnal-szemerédi theorem

Jozsef Balogh, Graeme Kemkes, Choongbum Lee, Stephen J. Young

Research output: Contribution to journalArticlepeer-review

Abstract

For a positive integer r ≥ 2, a Kr -factor of a graph is a collection vertex-disjoint copies of Kr which covers all the vertices of the given graph. The celebrated theorem of Hajnal and Szemerédi asserts that every graph on n vertices with minimum degree at least (1-1/r)n contains a Kr -factor. In this note, we propose investigating the relation between minimum degree and existence of perfect Kr -packing for edge-weighted graphs. The main question we study is the following. Suppose that a positive integer r ≥ 2 and a real t ε [0, 1] is given. What is the minimum weighted degree of Kn that guarantees the existence of a K r -factor such that every factor has total edge weight at least t(r2)? We provide some lower and upper bounds and make a conjecture on the asymptotics of the threshold as n goes to infinity.

Original languageEnglish (US)
Pages (from-to)346-350
Number of pages5
JournalCombinatorics Probability and Computing
Volume22
Issue number3
DOIs
StatePublished - May 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Towards a weighted version of the hajnal-szemerédi theorem'. Together they form a unique fingerprint.

Cite this