Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T19:04:48.843Z Has data issue: false hasContentIssue false
  • English
  • Français

Towards a Weighted Version of the Hajnal–Szemerédi Theorem

Published online by Cambridge University Press:  28 February 2013

JOZSEF BALOGH ,
GRAEME KEMKES ,
CHOONGBUM LEE  and
STEPHEN J. YOUNG
JOZSEF BALOGH
Affiliation:
Department of Mathematical Sciences, University of Illinois, Urbana, IL 61801, USA (e-mail: [email protected])
GRAEME KEMKES
Affiliation:
Department of Mathematics, Ryerson University, Toronto, ON, M5B 2K3, Canada (e-mail: [email protected])
CHOONGBUM LEE
Affiliation:
Department of Mathematics, University of California, Los Angeles, Los Angeles, CA 90095, USA (e-mail: [email protected])
STEPHEN J. YOUNG
Affiliation:
Department of Mathematics, University of Louisville, Louisville, KY, 40292, UCS (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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-\frac{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 Kr-factor such that every factor has total edge weight at least $$t\binom{r}{2}$?$ We provide some lower and upper bounds and make a conjecture on the asymptotics of the threshold as n goes to infinity.

Keywords

Primary 05C35Secondary 05C7005C7205D40
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 3 , May 2013 , pp. 346 - 350
Copyright
Copyright © Cambridge University Press 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Balogh, J., Kemkes, G., Lee, C. and Young, S. Towards a weighted version of the Hajnal–Szemerédi theorem. arXiv:1206.1376 [math.CO].Google Scholar
[2]Corrádi, K. and Hajnal, A. (1963) On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14 423–439.Google Scholar
[3]Daykin, D. E. and Häggkvist, R. (1981) Degrees giving independent edges in a hypergraph. Bull. Austral. Math. Soc. 23 103–109.Google Scholar
[4]Dirac, G. A. (1952) Some theorems on abstract graphs. Proc. London Math. Soc. (3) 269–81.CrossRefGoogle Scholar
[5]Hajnal, A. and Szemerédi, E. (1970) Proof of a conjecture of P. Erdős. In Combinatorial Theory and its Applications II: Proc. Colloq., Balatonfüred, 1969, North-Holland, pp. 601–623.Google Scholar
[6]Hàn, H., Person, Y. and Schacht, M. (2009) On perfect matchings in uniform hypergraphs with large minimum vertex degree. SIAM J. Discrete Math. 23 732–748.Google Scholar