On hitting all maximum cliques with an independent set
Landon Rabern · Journal of Graph Theory · 2010
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, Reed and Vetta's proof of Reed's conjecture for line graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 32–37, 2010