科研之友
微信
新浪微博
Facebook
分享链接
摘要
In 1998 the second author proved that there is an epsilon > 0 such that every graph satisfies chi <= left perpendicular(1 - epsilon)(Delta + 1) + epsilon omega right perpendicular. The first author recently proved that any graph satisfying omega > 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. Working from first principles, we omit only some five pages of proofs of known intermediate results (which appear in an extended version of this paper), and the proofs of Hall's Theorem, Brooks' Theorem, the Lovasz Local Lemma, and Talagrand's Inequality.
- 出版日期2016-1
- 单位McGill
