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.
Citation: Yufan Yuan. Progress on the Borodin–Kostochka conjecture: A structural approach via vertex partitions relative to a maximum clique[J]. AIMS Mathematics, 2026, 11(3): 8492-8506. doi: 10.3934/math.2026349
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.
| [1] |
O. Borodin, A. Kostochka, On an upper bound of a graph's chromatic number, depending on the graph's degree and density, J. Comb. Theory B, 23 (1977), 247–250. https://doi.org/10.1016/0095-8956(77)90037-5 doi: 10.1016/0095-8956(77)90037-5
|
| [2] |
R. Brooks, On colouring the nodes of a network, Math. Proc. Cambridge, 37 (1941), 194–197. https://doi.org/10.1017/S030500410002168X doi: 10.1017/S030500410002168X
|
| [3] |
R. Chen, K. Lan, X. Lin, Coloring hammer-free graphs with $\Delta - 1$ colors, Discrete Math., 347 (2023), 113823. https://doi.org/10.1016/j.disc.2023.113823 doi: 10.1016/j.disc.2023.113823
|
| [4] |
R. Chen, K. Lan, X. Lin, Y. Zhou, Borodin-Kostochka conjecture holds for odd-hole-free graphs, Graph. Combinator., 40 (2024), 26. https://doi.org/10.1007/s00373-024-02753-0 doi: 10.1007/s00373-024-02753-0
|
| [5] |
R. Chen, K. Lan, Y. Zhou, Coloring $\{P_2 \cup P_3, \text{house}\}$-free graphs with $\Delta - 1$ colors, Discret Appl. Math., 342 (2023), 12–18. https://doi.org/10.1016/j.dam.2023.09.003 doi: 10.1016/j.dam.2023.09.003
|
| [6] |
D. Cranston, L. Rabern, Coloring claw-free graphs with $\Delta-1$ colors, SIAM J. Discrete Math., 27 (2013), 534–549. https://doi.org/10.1137/12088015X doi: 10.1137/12088015X
|
| [7] |
D. Cranston, L. Rabern, Coloring a graph with $\Delta-1$ colors: conjectures equivalent to the Borodin-Kostochka conjecture that appear weaker, Eur. J. Combin., 44 (2015), 23–42. https://doi.org/10.1016/j.ejc.2014.09.006 doi: 10.1016/j.ejc.2014.09.006
|
| [8] |
D. Cranston, L. Rabern, Graphs with $\chi = \Delta$ have big cliques, SIAM J. Discrete Math., 29 (2015), 1792–1814. https://doi.org/10.1137/130929515 doi: 10.1137/130929515
|
| [9] |
D. Cranston, H. Lafayette, L. Rabern, Coloring $\{P_5, \text{gem}\}$-free graphs with $\Delta - 1$ colors, J. Graph Theor., 101 (2022), 633–642. https://doi.org/10.1002/jgt.22845 doi: 10.1002/jgt.22845
|
| [10] |
M. Dhurandhar, Improvement on Brooks' chromatic bound for a class of graphs, Discrete Math., 42 (1982), 51–56. https://doi.org/10.1016/0012-365X(82)90052-8 doi: 10.1016/0012-365X(82)90052-8
|
| [11] |
U. Gupta, D. Pradhan, Borodin-Kostochka's conjecture on $\{P_5, C_4\}$-free graphs, J. Appl. Math. Comput., 65 (2021), 877–884. https://doi.org/10.1007/s12190-020-01419-3 doi: 10.1007/s12190-020-01419-3
|
| [12] |
U. Gupta, D. Pradhan, Strengthening Brooks' chromatic bound on $P_6$-free graphs, Discret Appl. Math., 342 (2024), 334–346. https://doi.org/10.1016/j.dam.2023.09.031 doi: 10.1016/j.dam.2023.09.031
|
| [13] |
P. Haxell, C. MacDonald, Large cliques in graphs with high chromatic number, Discrete Math., 346 (2023), 113181. https://doi.org/10.1016/j.disc.2022.113181 doi: 10.1016/j.disc.2022.113181
|
| [14] |
H. Kierstead, J. Schmerl, The chromatic number of graphs which induce neither $K_{1, 3}$ nor $K_5 - e$, Discrete Math., 58 (1986), 253–262. https://doi.org/10.1016/0012-365X(86)90142-1 doi: 10.1016/0012-365X(86)90142-1
|
| [15] | A. Kostochka, Degree, density and chromatic number, Metody Diskretn. Anal., 35 (1980), 45–70. |
| [16] |
K. Lan, X. Lin, Borodin-Kostochka conjecture holds for $\overline{K_{1, 3}}$-free graphs, Discret Appl. Math., 356 (2024), 263–268. https://doi.org/10.1016/j.dam.2024.06.014 doi: 10.1016/j.dam.2024.06.014
|
| [17] |
K. Lan, F. Liu, Y. Zhou, Borodin-Kostochka conjecture on $\{P_2 \cup P_3, C_4\}$-free graphs, Graph. Combinator., 40 (2024), 123. https://doi.org/10.1007/s00373-024-02856-8 doi: 10.1007/s00373-024-02856-8
|
| [18] |
J. Long, K. Lan, Y. Wang, The chromatic number of $\{P_2 \cup P_3, \text{banner}\}$-free graphs, Appl. Math. Comput., 510 (2025), 129707. https://doi.org/10.1016/j.amc.2025.129707 doi: 10.1016/j.amc.2025.129707
|
| [19] | C. MacDonald, On finding large cliques when the chromatic number is close to the maximum degree, M.Sc Thesis, University of Waterloo, 2021. |
| [20] | N. Mozhan, Chromatic number of graphs with a density that does not exceed two-thirds of the maximal degree, Metody Diskretn. Anal., 39 (1983), 52–65. |
| [21] |
B. Reed, A strengthening of Brooks' theorem, J. Comb. Theory B, 76 (1999), 136–149. https://doi.org/10.1006/jctb.1998.1891 doi: 10.1006/jctb.1998.1891
|
| [22] | X. Xie, On the relation among the maximum degree, the chromatic number and the clique number, M.Sc Thesis, University of Waterloo, 2024. |
| [23] | Y. Yuan, J. Cao, C. Wen, Q. Sun, Coloring three graph classes with $\Delta - 1$ colors, Discret. Math. Algorit., in press. https://doi.org/10.1142/S1793830925501502 |
Figures(2)
Yufan Yuan. Progress on the Borodin–Kostochka conjecture: A structural approach via vertex partitions relative to a maximum clique[J]. AIMS Mathematics, 2026, 11(3): 8492-8506. doi: 10.3934/math.2026349
DownLoad: