Strengthening Brooks' chromatic bound on [formula omitted]-free graphs.

Brooks' theorem states that for a graph G , if Δ (G) ≥ 3 and ω (G) ≤ Δ (G) , then χ (G) ≤ Δ (G). In this paper, we show that this chromatic bound can be further strengthened on (P 6 , C 4 , H) -free graphs, where H ∈ { b u l l , d i a m o n d }. In particular, we prove that for a (P 6 , C 4 , b u l l) -free graph G , if Δ (G) ≥ 9 and ω (G) ≤ Δ (G) − 1 , then χ (G) ≤ Δ (G) − 1. We also prove that for a (P 6 , C 4 , d i a m o n d) -free graph G , if Δ (G) ≥ 5 and ω (G) ≤ Δ (G) − 1 , then χ (G) ≤ Δ (G) − 1. We also show that similar results hold for (P 10 , p a w) -free graphs and (P 5 , C 5) -free graphs. These results validate the Borodin–Kostochka conjecture on these graph classes. [ABSTRACT FROM AUTHOR]