A note on hitting maximum and maximal cliques with a stable set

Demetres Christofides, Katherine Edwards, Andrew D. King

It was recently proved that any graph satisfying $\omega >\frac{2}{3}(\Delta +1)$ contains a stable set hitting every maximum clique. In this note we prove that the same is true for graphs satis…