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


Abstract in English

The Borodin-Kostochka Conjecture states that for a graph $G$, if $Delta(G) geq 9$ and $omega(G) leq Delta(G)-1$, then $chi(G)leqDelta(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_1vee P_4$.

Download