Progress on the Borodin–Kostochka conjecture: A structural approach via vertex partitions relative to a maximum clique

Read full text Summarise with VIRAT
Authors: Yufan Yuan
Cited by: 0
References: 20

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