Turán number of four vertex-disjoint cliques

Abstract

Given a graph $H$, the Turán number $\mathrm{ex}(n,H)$ of $H$ is the maximum number of edges of an $n$-vertex simple graph containing no $H$ as a subgraph. Let $k{K}_p$ denote the disjoint union of $k$ copies of the complete graph $K_p$. In this paper, utilizing the idea of the proof of the Hajnal-Szemerédi Theorem and discharging, we determine the value $\mathrm{ex}(n,4K_p)$ for all $n$ and $p\ge 3$.

23 pages