An improvement on Brooks' Theorem

Abstract

We prove that $\chi (G)\le \max \omega (G),{\Delta }_2(G),(5/6)(\Delta (G)+1)$ for every graph $G$ with $\Delta (G)\ge 3$. Here ${\Delta }_2$ is the parameter introduced by Stacho that gives the largest degree that a vertex $v$ can have subject to the condition that $v$ is adjacent to a vertex whose degree is at least as large as its own. This upper bound generalizes both Brooks' Theorem and the Ore-degree version of Brooks' Theorem.