pith. sign in

arxiv: 1211.1410 · v1 · pith:4ZX66BRCnew · submitted 2012-11-06 · 💻 cs.DM · math.CO

A short proof that chi can be bounded ε away from Delta+1 towards ω

classification 💻 cs.DM math.CO
keywords epsilondeltaomegaauthoreverygraphproofproved
0
0 comments X
read the original abstract

In 1998 the second author proved that there is an $\epsilon>0$ such that every graph satisfies $\chi \leq \lceil (1-\epsilon)(\Delta+1)+\epsilon\omega\rceil$. 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 Hall's Theorem, Brooks' Theorem, the Lov\'asz Local Lemma, and Talagrand's Inequality.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.