A Note on Hitting Maximum and Maximal Cliques With a Stable Set. Issue 3 (17th July 2012) - Christofides, Demetres; Edwards, Katherine; King, Andrew D.
Abstract It was recently proved that any graph satisfying <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4q81x" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ω>23(Δ+1) contains a stable set hitting every maximum clique. In this note, we prove that the same is true for graphs satisfying <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4q7z9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ω≥23(Δ+1) unless the graph is the strong product of an odd hole and <inline-graphic mimetype="image" xlink:href="ark:/27927/pgg1zv4q7w6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Kω/2.We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.