Czechoslovak Mathematical Journal

Czechoslovak Mathematical Journal, first online, pp. 1-9

The Borodin-Kostochka conjecture holds for $\{P_2\cup P_3, \text{gem, bull}\}$-free graphs

Chuanshu WU

Received July 5, 2024. Published online October 1, 2026.

Abstract: Let $P_n$ denote the path on $n$ vertices. For two graphs $H_1$ and $H_2$, we use $H_1\cup H_2$ to denote the graph with vertex set $V(H_1)\cup V(H_2)$ and edge set $E(H_1)\cup E(H_2)$. Let $\Delta(G)$, $\chi(G)$ and $\omega(G)$ denote the maximum degree, chromatic number and clique number of a graph $G$, respectively. The Borodin-Kostochka conjecture says that for a graph $G$, if $\Delta(G)\geq9$, then $\chi(G)\leq\max\{\Delta(G)-1,\omega(G)\}$. We prove this conjecture for $\{P_2\cup P_3, \text{gem, bull}\}$-free graphs, where a gem is the graph that consists of a $P_4$ plus a vertex which is adjacent to all the vertices of that path, and a bull is a graph consisting of a triangle with two disjoint pendant edges.

Keywords: Borodin-Kostochka conjecture; chromatic number; induced subgraph

Classification MSC: 05C15

DOI: 10.21136/CMJ.2026.0278-24

PDF available at: Institute of Mathematics CAS

References:
[1] J. A. Bondy, U. S. R. Murty: Graph Theory. Graduate Texts in Mathematics 244. Springer, Berlin (2008). DOI 10.1007/978-1-84628-970-5 | MR 2368647 | Zbl 1134.05001
[2] O. V. Borodin, A. V. Kostochka: On an upper bound of a graph's chromatic number, depending on the graph's degree and density. J. Comb. Theory, Ser. B 23 (1977), 247-250. DOI 10.1016/0095-8956(77)90037-5 | MR 0469803 | Zbl 0336.05104
[3] R. L. Brooks: On colouring the nodes of a network. Proc. Camb. Philos. Soc. 37 (1941), 194-197. DOI 10.1017/S030500410002168X | MR 0012236 | Zbl 0027.26403
[4] P. A. Catlin: Embedding Subgraphs and Coloring Graphs Under Extremal Degree Conditions: Ph.D. Thesis. The Ohio State University, Columbus (1976). MR 2626461
[5] R. Chen, K. Lan, X. Lin: Coloring hammer-free graphs with $\Delta-1$ colors. Discrete Math. 347 (2024), Article ID 113823, 5 pages. DOI 10.1016/j.disc.2023.113823 | MR 4673277 | Zbl 1531.05070
[6] R. Chen, K. Lan, X. Lin, Y. Zhou: Borodin-Kostochka conjecture holds for odd-hole-free graphs. Graphs Comb. 40 (2024), Article ID 26, 5 pages. DOI 10.1007/s00373-024-02753-0 | MR 4703467 | Zbl 1532.05063
[7] R. Chen, K. Lan, Y. Zhou: Coloring $\{P_2\cup P_3,\rm{house}\}$-free graphs with $\Delta-1$ colors. Discrete Appl. Math. 342 (2024), 12-18. DOI 10.1016/j.dam.2023.09.003 | MR 4641005 | Zbl 1531.05071
[8] S. A. Choudum, T. Karthick, M. A. Shalu: Perfect coloring and linearly $\chi$-bound $P_6$-free graphs. J. Graph Theory 54 (2007), 293-306. DOI 10.1002/jgt.20212 | MR 2292667 | Zbl 1121.05045
[9] M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas: The strong perfect graph theorem. Ann. Math. (2) 164 (2006), 51-229. DOI 10.4007/annals.2006.164.51 | MR 2233847 | Zbl 1112.05042
[10] M. Chudnovsky, P. Seymour: The structure of claw-free graphs. Surveys in Combinatorics 2005. London Mathematical Society Lecture Note Series 327. Cambridge University Press, Cambridge (2005), 153-171. DOI 10.1017/CBO9780511734885.008 | MR 2187738 | Zbl 1109.05092
[11] D. W. Cranston, H. Lafayette, L. Rabern: Coloring $(P_5,\rm{gem})$-free graphs with $\Delta-1$ colors. J. Graph Theory 101 (2022), 633-642. DOI 10.1002/jgt.22845 | MR 4520051 | Zbl 1522.05104
[12] D. W. Cranston, L. Rabern: Coloring claw-free graphs with $\Delta-1$ colors. SIAM J. Discrete Math. 27 (2013), 534-549. DOI 10.1137/12088015X | MR 3032933 | Zbl 1268.05069
[13] G. A. Dirac: Note on the colouring of graphs. Math. Z. 54 (1951), 347-353. DOI 10.1007/BF01238034 | MR 0046030 | Zbl 0043.38502
[14] U. K. Gupta, D. Pradhan: Borodin-Kostochka's conjecture on $(P_5,C_4)$-free graphs. J. Appl. Math. Comput. 65 (2021), 877-884. DOI 10.1007/s12190-020-01419-3 | MR 4208191 | Zbl 1475.05068
[15] U. K. Gupta, D. Pradhan: Strengthening Brooks' chromatic bound on $P_6$-free graphs. Discrete Appl. Math. 342 (2024), 334-346. DOI 10.1016/j.dam.2023.09.031 | MR 4651830 | Zbl 1531.05078
[16] A. V. Kostochka: The degree, density and chromatic number of graphs. Metody Diskretn. Anal. 35 (1980), 45-70. (In Russian.) MR 0625389 | Zbl 0459.05038
[17] K. Lan, X. Lin: Borodin-Kostochka conjecture holds for $\overline{K_{1,3}}$-free graphs. Discrete Appl. Math. 356 (2024), 263-268. DOI 10.1016/j.dam.2024.06.014 | MR 4760157 | Zbl 1544.05036
[18] K. Lan, F. Liu, Y. Zhou: Borodin-Kostochka's conjecture on $\{P_2\cup P_3,C_4\}$-free graphs. Graphs Comb. 40 (2024), Article ID 123, 12 pages. DOI 10.1007/s00373-024-02856-8 | MR 4822710 | Zbl 1553.05063
[19] B. Reed: A strengthening of Brooks' theorem. J. Comb. Theory, Ser. B 76 (1999), 136-149. DOI 10.1006/jctb.1998.1891 | MR 1699199 | Zbl 0935.05045
[20] D. B. West: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). MR 1367739 | Zbl 0845.05001

Affiliations: Chuanshu Wu, Center for Discrete Mathematics, Fuzhou University, 2 Wulongjiang North Avenue University Town, Fuzhou, Fujian Province, 350108 P. R. China, e-mail: cswu97@126.com

Springer subscribers can access the papers on Springer website.

[List of online first articles] [Contents of Czechoslovak Mathematical Journal] [Full text of the older issues of Czechoslovak Mathematical Journal at DML-CZ]

PDF available at:

Institute of Mathematics CAS
fulltext not available