Improving the Caro-Wei bound and applications to Turán stability

Abstract

We prove that if $G$ is a graph and $f(v)\le 1/(d(v)+1/2)$ for each $v\in V(G)$, then either $G$ has an independent set of size at least ${\sum }_{v\in V(G)}f(v)$ or $G$ contains a clique $K$ such that ${\sum }_{v\in K}f(v)>1$. This result implies that for any $\sigma \le 1/2$, if $G$ is a graph and every clique $K\subseteq V(G)$ has at most $(1-\sigma )(|K|-\sigma )$ simplicial vertices, then $\alpha (G)\ge {\sum }_{v\in V(G)}1/(d(v)+1-\sigma )$. Letting $\sigma =0$ implies the famous Caro-Wei Theorem, and letting $\sigma =1/2$ implies that if fewer than half of the vertices in each clique of $G$ are simplicial, then $\alpha (G)\ge {\sum }_{v\in V(G)}1/(d(v)+1/2)$, which is tight for the 5-cycle. When applied to the complement of a graph, this result implies the following new Tur\' an stability result. If $G$ is a $K_{r+1}$-free graph with more than $(1-1/r)n^2/2-n/4$ edges, then $G$ contains an independent set $I$ such that at least half of the vertices in $I$ are complete to $G-I$. Applying this stability result iteratively provides a new proof of the stability version of Tur\' an's Theorem in which $K_{r+1}$-free graphs with close to the extremal number of edges are $r$-partite.

16 pages. Derived from the preprint arxiv:1811.11806v1