At Least Half Of All Graphs Satisfy χ\leq {1/4}ω+ {3/4}Δ+ 1

Abstract

We prove that for any graph G at least one of G or $\bar{G}$ satisfies $\chi \le 1/4\omega +3/4\Delta +1$. In particular, self-complementary graphs satisfy this bound.