On hitting all maximum cliques with an independent set
On hitting all maximum cliques with an independent set
We prove that every graph G for which has an independent set I such that ω(G−I)<ω(G). It follows that a minimum counterexample G to Reed's conjecture satisfies and hence also . This also applies to restrictions of Reed's conjecture to hereditary graph classes, and in particular generalizes and simplifies King, …