Progress on the Borodin–Kostochka conjecture: A structural approach via vertex partitions relative to a maximum clique
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
The Borodin-Kostochka conjecture states that for any graph $ G $ with $ \Delta(G) \geq 9 $, we have $ \chi(G) \leq \max\{\Delta(G)-1, \omega(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 $ \chi(G) \leq \Delta(G)-1 $. Consequently, we confirm the conjecture for any $ \overline{K_{1, t}} $-free graph $ G $ with $ t \geq 3 $ and $ \Delta(G) \geq 2t+1 $, strengthening and extending the recent work of Lan and Lin in 2024.
Fields of Study & Subjects
Advanced Graph Theory Research
Graph Labeling and Dimension Problems
Limits and Structures in Graph Theory
Publication details
- Journal / source
- AIMS Mathematics
- Volume
- 11
- Issue
- 3
- Pages
- 8492–8506
- Publication date
- 1 January 2026
- Language
- EN