In 1998 the second author proved that there is an $epsilon>0$ such that every graph satisfies $chi leq lceil (1-epsilon)(Delta+1)+epsilonomegarceil$. The first author recently proved that any graph satisfying $omega > frac 23(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 Halls Theorem, Brooks Theorem, the Lovasz Local Lemma, and Talagrands Inequality.
تحميل البحث