A short proof that $\chi$ can be bounded $\epsilon$ away from $\Delta +1$ towards $\omega$

Abstract

In 1998 the second author proved that there is an $\epsilon >0$ such that every graph satisfies $\chi \le \lceil (1-\epsilon )(\Delta +1)+\epsilon \omega \rceil$. The first author recently proved that any graph satisfying $\omega >\frac{2}{3}(\Delta +1)$ contains a stable set intersecting every maximum clique. In this note we exploit the latter result to give a much shorter, simpler proof of the former. We include, as a certificate of simplicity, an appendix that proves all intermediate results with the exception of Hall's Theorem, Brooks' Theorem, the Lovász Local Lemma, and Talagrand's Inequality.

10 pages. arXiv admin note: text overlap with arXiv:0911.1741