2012/11/06 by Andrew D. King, King, Andrew D., Bruce A. Reed +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1211.1410
10 pages. arXiv admin note: text overlap with arXiv:0911.1741
arxiv created 2012/11/06 · arxiv updated 2012/11/08
In 1998 the second author proved that there is an ε>0 such that every graph satisfies χ≤ \lceil (1-ε)(Δ+1)+εω\rceil. The first author recently proved that any graph satisfying ω> \frac 23(Δ+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.