On the stability of graph independence number

Abstract

Let $G$ be a graph on $n$ vertices of independence number $\alpha (G)$ such that every induced subgraph of $G$ on $n-k$ vertices has an independent set of size at least $\alpha (G)-\ell$. What is the largest possible $\alpha (G)$ in terms of $n$ for fixed $k$ and $\ell$? We show that $\alpha (G)\le n/2+C_{k,\ell }$, which is sharp for $k-\ell \le 2$. We also use this result to determine new values of the Erdős--Rogers function.

arXiv comment16 pages, 2 figures

References in corpus (1)

• Improved bounds for the Erdős-Rogers function

Cited by in corpus (1)

• Hitting all maximum independent sets