Borodin-Kostochka conjecture for a family of P₆-free graphs

Abstract: Borodin and Kostochka conjectured that every graph

G

with

D e l t a g e 9

satisfies

c h i l e

max

o m e g a, D e l t a - 1

. Gupta and Pradhan proved the Borodin-Kostochka conjecture for (

P_{5}

,

C_{4}

)-free graphs. In this note, we prove the Borodin-Kostochka conjecture for (

P_{6}

, apple, torch)-free graphs, that is, graphs with no induced

P_{6}

, no induced

C_{5}

with a hanging edge, and no induced

C_{5}

and

C_{4}

sharing exactly two edges. This generalizes the result of Gupta and Pradhan from the perspective of allowing the existence of

P_{5}

.

This page was built for publication: Borodin-Kostochka conjecture for a family of $P_6$-free graphs