- Journal Article
A classical result by Hajnal and Szemerédi from 1970 determines the minimal degree conditions necessary to guarantee for a graph to contain a Kr-factor. Namely, any graph on n vertices, with minimum degree δ(G) ≥ (1 − 1/r) n and r dividing n has a Kr-factor. This result is tight but the extremal examples are unique in that they all have a large independent set which is the bottleneck. Nenadov and Pehova showed that by requiring a sub-linear independence number the minimum degree condition in the Hajnal-Szemerédi theorem can be improved. We show that, with the same minimum degree and sub-linear independence number, we can find a clique-factor with double the clique size. More formally, we show for every r ∈ N and constant μ > 0 there is a positive constant γ such that every graph G on n vertices with δ(G) ≥ (1 − 2/r + μ) n and α(G) < γn has a Kr-factor. We also give examples showing the minimum degree condition is asymptotically best possible. © 2020 Elsevier Inc. Show more
Journal / seriesJournal of Combinatorial Theory. Series B
Pages / Article No.
SubjectGraph embedding; Hajnal-Szemerédi theorem; Ramsey Turán theory
Organisational unit03672 - Steger, Angelika / Steger, Angelika
169242 - Saturation Games and Robust Random Structures (SNF)
MoreShow all metadata