{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T01:34:00Z","timestamp":1778031240032,"version":"3.51.4"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T00:00:00Z","timestamp":1731283200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T00:00:00Z","timestamp":1731283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s00373-024-02856-8","type":"journal-article","created":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T07:56:40Z","timestamp":1731311800000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Borodin\u2013Kostochka\u2019s Conjecture on $$\\{P_2\\cup P_3,C_4\\}$$-Free Graphs"],"prefix":"10.1007","volume":"40","author":[{"given":"Kaiyang","family":"Lan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feng","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yidong","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,11,11]]},"reference":[{"key":"2856_CR1","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84628-970-5","volume-title":"Graph Theory","author":"J Bondy","year":"2008","unstructured":"Bondy, J., Murty, U.S.R.: Graph Theory. Graduate Texts in Mathematics, vol. 244. Springer, Berlin (2008)"},{"key":"2856_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0095-8956(77)90037-5","volume":"23","author":"O Borodin","year":"1997","unstructured":"Borodin, O., Kostochka, A.: On an upper bound of a graph\u2019s chromatic number, depending on the graph\u2019s degree and density. J. Combin. Theory Ser. B 23, 247\u2013250 (1997)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2856_CR3","series-title":"Mathematical Proceedings of the Cambridge Philosophical Society","first-page":"194","volume-title":"On Colouring the Nodes of a Network","author":"R Brooks","year":"1941","unstructured":"Brooks, R.: On Colouring the Nodes of a Network. Mathematical Proceedings of the Cambridge Philosophical Society, vol. 37, pp. 194\u2013197. Cambridge University Press, Cambridge (1941)"},{"key":"2856_CR4","unstructured":"Catlin, P.: Embedding subgraphs and coloring graphs under extremal degree conditions. ProQuest LLC, Ann Arbor, MI, Thesis (Ph.D.) The Ohio State University (1976)"},{"key":"2856_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"key":"2856_CR6","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1002\/jgt.22845","volume":"101","author":"D Cranston","year":"2022","unstructured":"Cranston, D., Lafayette, H., Rabern, L.: Coloring $$\\{P_5, \\text{ gem }\\}$$-free graphs with $$\\Delta -1$$ colors. J. Graph Theory 101, 633\u2013642 (2022)","journal-title":"J. Graph Theory"},{"key":"2856_CR7","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1137\/12088015X","volume":"27","author":"D Cranston","year":"2013","unstructured":"Cranston, D., Rabern, L.: Coloring claw-free graphs with $$\\Delta -1$$ colors. SIAM J. Discret. Math. 27, 534\u2013549 (2013)","journal-title":"SIAM J. Discret. Math."},{"key":"2856_CR8","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF01238034","volume":"54","author":"G Dirac","year":"1951","unstructured":"Dirac, G.: Note on the colouring of graphs. Math. Z. 54, 347\u2013353 (1951)","journal-title":"Math. Z."},{"key":"2856_CR9","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1007\/s12190-020-01419-3","volume":"65","author":"U Gupta","year":"2021","unstructured":"Gupta, U., Pradhan, D.: Borodin-Kostochka\u2019s conjecture on $$\\{P_5, C_4\\}$$-free graphs. J. Appl. Math. Comput. 65, 877\u2013884 (2021)","journal-title":"J. Appl. Math. Comput."},{"key":"2856_CR10","first-page":"45","volume":"35","author":"A Kostochka","year":"1980","unstructured":"Kostochka, A.: Degree, density, and chromatic number. Metody Diskret. Anal. 35, 45\u201370 (1980)","journal-title":"Metody Diskret. Anal."},{"key":"2856_CR11","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","first-page":"+326","DOI":"10.1007\/978-3-642-04016-0","volume-title":"Graph Colouring and the Probabilistic Method","author":"M Molloy","year":"2002","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Algorithms and Combinatorics, vol. 23, p. +326. Springer, Berlin (2002)"},{"key":"2856_CR12","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1006\/jctb.1998.1891","volume":"76","author":"B Reed","year":"1999","unstructured":"Reed, B.: A strengthening of Brooks\u2019 theorem. J. Combin. Theory Ser. B 76, 136\u2013149 (1999)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2856_CR13","volume-title":"Introduction to Graph Theory","author":"D West","year":"2000","unstructured":"West, D.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs (2000)","edition":"2"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02856-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02856-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02856-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T20:07:32Z","timestamp":1733515652000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02856-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,11]]},"references-count":13,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["2856"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02856-8","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,11]]},"assertion":[{"value":"24 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 October 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"123"}}