A note on Reed's conjecture

Abstract

In \cite{reed97}, Reed conjectures that the inequality $\chi (G)\le \lceil 1/2(\omega (G)+\Delta (G)+1)\rceil$ holds for any graph $G$. We prove this holds for a graph $G$ if $\bar{G}$ is disconnected. From this it follows that the conjecture holds for graphs with $\chi (G)>\lceil \frac{|G|}{2}\rceil$. In addition, the conjecture holds for graphs with $\Delta (G)\ge |G|-\sqrt{|G|+2\alpha (G)+1}$. In particular, Reed's conjecture holds for graphs with $\Delta (G)\ge |G|-\sqrt{|G|+7}$. Using these results, we proceed to show that if $|G|$ is an even order counterexample to Reed's conjecture, then $\bar{G}$ has a 1-factor. Hence, for any even order graph $G$, if $\chi (G)>1/2(\omega (G)+\Delta (G)+1)+1$, then $\bar{G}$ is matching covered.