The Borodin-Kostochka Conjecture states that for a graph G, if Δ(G)≥9, then χ(G)≤max\Δ(G)-1,ω(G)\. We use Pₜ and Cₜ to denote a path and a cycle on t vertices, respectively. Let C=v₁v₂v₃v₄v₅v₁ be an induced C₅. A { C₅⁺} is a graph obtained from C by adding a C₃=xyzx and a P₂=t₁t₂ such that (1) x and y are both exactly adjacent to v₁,v₂,v₃ in $V(C)$, z is exactly adjacent to v₂ in $V(C)$, t₁ is exactly adjacent to v₄,v₅ in $V(C)$ and t₂ is exactly adjacent to v₁,v₄,v₅ in $V(C)$, (2) t₁ is exactly adjacent to z in ,y,z\ and t₂ has no neighbors in ,y,z\. In this paper, we show that the Borodin-Kostochka Conjecture holds for (P₆,C₄,H)-free graphs, where H∈ ₇,C₅⁺\. This generalizes some results of Gupta and Pradhan in {GP21,GP24}.
No takes yet. Share an insight, caveat, or question.
Chen et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: