A Note on Hitting Maximum and Maximal Cliques With a Stable Set. Issue 3 (17th July 2012) - Christofides, Demetres
Abstract It was recently proved that any graph satisfying ω>23(Δ+1) contains a stable set hitting every maximum clique. In this note, we prove that the same is true for graphs satisfying ω≥23(Δ+1) unless the graph is the strong product of an odd hole and Kω/2.We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.