Squared chromatic and stability numbers without claws or large cliques.
Wouter Cames van Batenburg, Ross J. Kang · arXiv (Cornell University) · 2016
Let $G$ be a claw-free graph on $n$ vertices with clique number $\omega$. We prove the following for the square $G^2$ of $G$. If $\omega\le 3$, then its chromatic number satisfies $\chi(G^2)\le 10$ while its stability number satisfies $\alpha(G^2)\ge n/9$ unless one of its components is a $10$-vertex clique. If $\omega \le 4$, then $\chi(G^2) \le 22$ and $\alpha(G^2)\ge n/20$. This work is motivated by a conjecture of Erd\H{o}s and Ne\v{s}et\v{r}il and provides further evidence for a strengthened form of that conjecture.