{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T13:54:18Z","timestamp":1752674058964,"version":"3.41.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T00:00:00Z","timestamp":1733184000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T00:00:00Z","timestamp":1733184000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12101117"],"award-info":[{"award-number":["12101117"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004608","name":"Natural Science Foundation of Jiangsu Province","doi-asserted-by":"publisher","award":["BK20200344"],"award-info":[{"award-number":["BK20200344"]}],"id":[{"id":"10.13039\/501100004608","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,2]]},"DOI":"10.1007\/s00373-024-02866-6","type":"journal-article","created":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T19:45:01Z","timestamp":1733255101000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Non-perfect $$(P_5, C_5, K_5-e)$$-Free Graphs are 5-Colorable"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1424-7042","authenticated-orcid":false,"given":"Yian","family":"Xu","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,3]]},"reference":[{"key":"2866_CR1","doi-asserted-by":"crossref","unstructured":"Char, A., Karthick, T.: Improved bounds on the chromatic number of ($$P_5$$, flag)-free graphs. Discrete Math. 346, 113501 (2023)","DOI":"10.1016\/j.disc.2023.113501"},{"issue":"4","key":"2866_CR2","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1002\/jgt.20212","volume":"54","author":"SA Choudum","year":"2007","unstructured":"Choudum, S.A., Karthick, T., Shalu, M.A.: Perfect coloring and linearly $$\\chi $$-bound $$P_6$$-free graphs. J. Graph Theory 54(4), 293\u2013306 (2007)","journal-title":"J. Graph Theory"},{"issue":"1","key":"2866_CR3","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. (2) 164(1), 51\u2013229 (2006)","journal-title":"Ann. Math. (2)"},{"issue":"3","key":"2866_CR4","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.jctb.2009.10.001","volume":"100","author":"M Chudnovsky","year":"2010","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: $$K_4$$-free graphs with no odd holes. J. Combin. Theory Ser. B 100(3), 313\u2013331 (2010)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"2866_CR5","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1002\/jgt.22367","volume":"90","author":"M Chudnovsky","year":"2019","unstructured":"Chudnovsky, M., Sivaraman, V.: Perfect divisibility and 2-divisibility. J. Graph Theory 90(1), 54\u201360 (2019)","journal-title":"J. Graph Theory"},{"key":"2866_CR6","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.disc.2022.113004","volume":"345","author":"W Dong","year":"2022","unstructured":"Dong, W., Xu, B., Xu, Y.: On the chromatic number of some $$P_5$$-free graphs. Discrete Math. 345, 10 (2022). (Paper No. 113004, 11)","journal-title":"Discrete Math."},{"key":"2866_CR7","doi-asserted-by":"publisher","first-page":"34","DOI":"10.4153\/CJM-1959-003-9","volume":"11","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P.: Graph theory and probability. Can. J. Math. 11, 34\u201338 (1959)","journal-title":"Can. J. Math."},{"key":"2866_CR8","unstructured":"Erd\u0151s, P., Hajnal, A.. On., spanned subgraphs of graphs. In Contributions to graph theory and its applications (Internat. Colloq., Oberhof, 1977) (German). Tech. Hochschule Ilmenau, Ilmenau, pp. 80\u201396 (1977)"},{"key":"2866_CR9","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P., Hajnal, A.: Ramsey-type theorems. vol.\u00a025. 1989, pp.\u00a037\u201352. Combinatorics and complexity (Chicago, IL, 1987)","DOI":"10.1016\/0166-218X(89)90045-0"},{"issue":"6","key":"2866_CR10","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1016\/j.disc.2012.12.019","volume":"313","author":"L Esperet","year":"2013","unstructured":"Esperet, L., Lemoine, L., Maffray, F., Morel, G.: The chromatic number of $$\\{P_5, K_4\\}$$-free graphs. Discrete Math. 313(6), 743\u2013754 (2013)","journal-title":"Discrete Math."},{"key":"2866_CR11","unstructured":"Gei\u00dfer, M. Colorings of $$P_5$$-free graphs. PhD Thesis (2022)"},{"issue":"2\u20133","key":"2866_CR12","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0012-365X(03)00197-3","volume":"272","author":"S Gravier","year":"2003","unstructured":"Gravier, S., Ho\u00e0ng, C.T., Maffray, F.: Coloring the hypergraph of maximal cliques of a graph with no long path. Discrete Math. 272(2\u20133), 285\u2013290 (2003)","journal-title":"Discrete Math."},{"key":"2866_CR13","unstructured":"Gy\u00e1rf\u00e1s, A.: On Ramsey covering-numbers. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd\u0151s on his 60th birthday), Vol. II. 1975, pp.\u00a0801\u2013816. Colloq. Math. Soc. Jan\u00f3s Bolyai, Vol. 10"},{"key":"2866_CR14","doi-asserted-by":"crossref","unstructured":"Gy\u00e1rf\u00e1s, A.: Problems from the world surrounding perfect graphs. In: Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985) (1987), vol.\u00a019, pp.\u00a0413\u2013441 (1988)","DOI":"10.4064\/am-19-3-4-413-441"},{"issue":"2","key":"2866_CR15","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1007\/s10878-014-9792-3","volume":"31","author":"DS Malyshev","year":"2016","unstructured":"Malyshev, D.S.: Two cases of polynomial-time solvability for the coloring problem. J. Comb. Optim. 31(2), 833\u2013845 (2016)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"2866_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-018-1999-0","volume":"35","author":"I Schiermeyer","year":"2019","unstructured":"Schiermeyer, I., Randerath, B.: Polynomial $$\\chi $$-binding functions and forbidden induced subgraphs: a survey. Graphs Combin. 35(1), 1\u201331 (2019)","journal-title":"Graphs Combin."},{"issue":"3","key":"2866_CR17","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/jgt.22601","volume":"95","author":"A Scott","year":"2020","unstructured":"Scott, A., Seymour, P.: A survey of $$\\chi $$-boundedness. J. Graph Theory 95(3), 473\u2013504 (2020)","journal-title":"J. Graph Theory"},{"key":"2866_CR18","doi-asserted-by":"crossref","unstructured":"Scott, A., Seymour, P., Spirkl, S.: Polynomial bounds for chromatic number. $$IV$$. $$A$$ near-polynomial bound for excluding the five-vertex path, arXiv:2110.00278, (2022)","DOI":"10.1007\/s00493-023-00015-w"},{"key":"2866_CR19","unstructured":"Sumner, D.P.: Subtrees of a graph and the chromatic number. In: The Theory and Applications of Graphs (Kalamazoo, Mich., 1980), pp. 557\u2013576. Wiley, New York (1980)"},{"issue":"2","key":"2866_CR20","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1002\/jgt.22214","volume":"88","author":"N Trotignon","year":"2018","unstructured":"Trotignon, N., Pham, L.A.: $$\\chi $$-bounds, operations, and chords. J. Graph Theory 88(2), 312\u2013336 (2018)","journal-title":"J. Graph Theory"},{"key":"2866_CR21","doi-asserted-by":"crossref","unstructured":"Xu, Y.: The chromatic number of ($$P_5$$, HVN)-free graphs, arXiv:2204.06460, (2022)","DOI":"10.1142\/S1793830922500902"},{"key":"2866_CR22","first-page":"9","volume":"461","author":"Y Xu","year":"2024","unstructured":"Xu, Y.: Coloring graphs without induced $$P_5$$ or $$K_5-e$$. Appl. Math. Comput. 461, 9 (2024). (Paper No. 128314)","journal-title":"Appl. Math. Comput."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02866-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02866-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02866-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T04:22:37Z","timestamp":1748319757000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02866-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,3]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["2866"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02866-6","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2024,12,3]]},"assertion":[{"value":"21 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"3"}}