On hitting all maximum cliques with an independent set

We prove that every graph $G$ for which $\omega (G)\ge 3\mathrm{/}4(\mathrm{\Delta }(G)+1)$, has an independent set $I$ such that $\omega (G-I)<\omega (G)$. It follows that a minimum counterexample $G$ to Reed’s conjecture satisfies $\omega(G) < 3/4(\Delta(G) + 1)$andhencealso$\chi(G) > \lceil 7/6\omega(G) \rceil$. We also prove that if for every induced subgraph $H$ of $G$ we have $\chi(H) \leq \max{\lceil 7/6\omega(H) \rceil, \lceil \frac{\omega(H) + \Delta(H) + 1}{2}\rceil}$,thenwealsohave$\chi(G) \leq \lceil \frac{\omega(G) + \Delta(G) + 1}{2}\rceil$. This gives a generic proof of the upper bound for line graphs of multigraphs proved by King et al.