A Note On Reed's Conjecture
Landon Rabern · SIAM Journal on Discrete Mathematics · 2008
In [J. Graph Theory, 27 (1998), pp. 177–212], Reed conjectures that every graph satisfies $\chi \leq \lceil \frac{\omega + \Delta + 1}{2} \rceil$. We prove that this holds for graphs with disconnected complement. Combining this fact with a result of Molloy proves the conjecture for graphs satisfying $\chi > \lceil\frac{n}{2}\rceil$. Generalizing this we prove that the conjecture holds for graphs satisfying $\chi > \frac{n + 3 - \alpha}{2}$. It follows that the conjecture holds for graphs satisfying $\Delta \geq n + 2 - (\alpha + \sqrt{n + 5 - \alpha})$. In the final section, we show that if G is an even order counterexample to Reed's conjecture, then $\overline{G}$ has a 1-factor.