Coloring $\Delta$-Critical Graphs With Small High Vertex Cliques

Abstract

We prove that $K_{\chi (G)}$ is the only critical graph $G$ with $\chi (G)\ge \Delta (G)\ge 6$ and $\omega (\mathcal{H}(G))\le \lfloor \frac{\Delta (G)}{2}\rfloor -2$. Here $\mathcal{H}(G)$ is the subgraph of $G$ induced on the vertices of degree at least $\chi (G)$. Setting $\omega (\mathcal{H}(G))=1$ proves a conjecture of Kierstead and Kostochka.