E-resources
Peer reviewed
-
Gupta, Uttam K.; Pradhan, Dinabandhu
Discrete Applied Mathematics, 01/2024, Volume: 342Journal Article
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 (P6,C4,H)-free graphs, where H∈{bull,diamond}. In particular, we prove that for a (P6,C4,bull)-free graph G, if Δ(G)≥9 and ω(G)≤Δ(G)−1, then χ(G)≤Δ(G)−1. We also prove that for a (P6,C4,diamond)-free graph G, if Δ(G)≥5 and ω(G)≤Δ(G)−1, then χ(G)≤Δ(G)−1. We also show that similar results hold for (P10,paw)-free graphs and (P5,C5)-free graphs. These results validate the Borodin–Kostochka conjecture on these graph classes.
