Article contents
Local Density in Graphs with Forbidden Subgraphs
Published online by Cambridge University Press: 17 March 2003
Abstract
A celebrated theorem of Turán asserts that every graph on n vertices with more than $\frac{r\,{-}\,1}{2r}n^2$ edges contains a copy of a complete graph $K_r+1$. In this paper we consider the following more general question. Let G be a $K_r+1-free graph of order n and let α be a constant, 0<α≤1. How dense can every induced subgraph of G on αn vertices be? We prove the following local density extension of Turán's theorem.
For every integer $r\geq 2$ there exists a constant $c_r < 1$ such that, if $c_r < \alpha < 1$ and every αn vertices of G span more than
\[ \frac{r\,{-}\,1}{2r}(2\alpha -1)n^2\vspace*{7pt} \]
edges, then G contains a copy of $K_r+1$. This result is clearly best possible and answers a question of Erdős, Faudree, Rousseau and Schelp [5].
In addition, we prove that the only $K_r+1-free graph of order n, in which every αn vertices span at least $\frac{r\,{-}\,1}{2r}(2\alpha -1)n^2$ edges, is a Turán graph. We also obtain the local density version of the Erdős–Stone theorem.
- Type
- Research Article
- Information
- Copyright
- 2003 Cambridge University Press
- 7
- Cited by