Coloring $(P_5,\text{gem})$-free graphs with $\Delta -1$ colors

Abstract

The Borodin-Kostochka Conjecture states that for a graph $G$, if $\Delta (G)\ge 9$ and $\omega (G)\le \Delta (G)-1$, then $\chi (G)\le \Delta (G)-1$. We prove the Borodin-Kostochka Conjecture for $(P_5,\text{gem})$-free graphs, i.e., graphs with no induced $P_5$ and no induced $K_1\vee P_4$.

8 pages, 6 figures