Cliques and High Odd Holes in Graphs with Chromatic Number Equal to Maximum Degree

Abstract

We give a uniform and self-contained proof that if $G$ is a connected graph with $\chi (G)=\Delta (G)$ and $G\ne \overline{C_7}$, then $G$ contains either $K_{\Delta (G)}$ or an odd hole where every vertex has degree at least $\Delta (G)-1$ in $G$. This was previously proved in series of two papers by Chen, Lan, Lin, and Zhou, who used the Strong Perfect Graph Theorem for the cases $\Delta (G)=4,5,6$.