Publications
Sort:
Open Access Research Article Issue
Progress on the Borodin–Kostochka conjecture: A structural approach via vertex partitions relative to a maximum clique
AIMS Mathematics 2026, 11(3): 8492-8506
Published: 15 March 2026
Abstract PDF (502.5 KB) Collect
Downloads:0

The Borodin-Kostochka conjecture states that for any graph G with Δ ( G ) 9, we have χ ( G ) max { Δ ( G ) 1 , ω ( G ) }. In this paper, we study the structure of potential counterexamples by partitioning vertices according to the number of neighbors they have in a fixed maximum clique. This approach provides a sufficient condition for χ ( G ) Δ ( G ) 1. Consequently, we confirm the conjecture for any K 1 , t ¯ -free graph G with t 3 and Δ ( G ) 2 t + 1, strengthening and extending the recent work of Lan and Lin in 2024.

Total 1