






















A seminal result of Hajnal and Szemerédi states that if a graph $G$ with $n$ vertices has minimum degree $δ(G) \ge (r-1)n/r$ for some integer $r \ge 2$, then $G$ contains a $K_r$-factor, assuming $r$ divides $n$. Extremal examples which show optimality of the bound on $δ(G)$ are very structured and, in particular, contain large independent sets. In analogy to the Ramsey-Turán theory, Balogh, Molla, and Sharifzadeh initiated the study of how the absence of such large independent sets influences sufficient minimum degree. We show the following two related results: $\bullet$ For any $r > \ell \ge 2$, if $G$ is a graph satisfying $δ(G) \ge (r - \ell)n/(r - \ell + 1) +Ω(n)$ and $α_\ell(G)=o(n)$, that is, a largest $K_\ell$-free induced subgraph has at most $o(n)$ vertices, then $G$ contains a $K_r$-factor. This is optimal for $\ell = r - 1$ and extends a result of Balogh, Molla, and Sharifzadeh who considered the case $r = 3$. $\bullet$ If a graph $G$ satisfies $δ(G) =Ω(n)$ and $α_r^*(G) =o(n)$, that is, every induced $K_r$-free $r$-partite subgraph of $G$ has at least one vertex class of size $o(n)$, then it contains a $K_r$-factor. A similar statement is proven for a general graph $H$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。