{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:49:29Z","timestamp":1780822169131,"version":"3.54.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,25]],"date-time":"2024-02-25T00:00:00Z","timestamp":1708819200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,2,25]],"date-time":"2024-02-25T00:00:00Z","timestamp":1708819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2022-03697"],"award-info":[{"award-number":["RGPIN-2022-03697"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["DGECR-2022-00446"],"award-info":[{"award-number":["DGECR-2022-00446"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2018-06178"],"award-info":[{"award-number":["RGPIN-2018-06178"]}],"id":[{"id":"10.13039\/501100000038","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":[[2024,4]]},"DOI":"10.1007\/s00373-024-02756-x","type":"journal-article","created":{"date-parts":[[2024,2,25]],"date-time":"2024-02-25T09:01:58Z","timestamp":1708851718000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Infinite Families of k-Vertex-Critical ($$P_5$$, $$C_5$$)-Free Graphs"],"prefix":"10.1007","volume":"40","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1020-2883","authenticated-orcid":false,"given":"Ben","family":"Cameron","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ch\u00ednh","family":"Ho\u00e0ng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,2,25]]},"reference":[{"key":"2756_CR1","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations (Proceedings of the Symposium, IBM Thomas J. Watson Research Center, Yorktown Heights, 1972), pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"2756_CR2","doi-asserted-by":"publisher","first-page":"61","DOI":"10.11575\/cdm.v2i1.61890","volume":"2","author":"M Kami\u0144ski","year":"2007","unstructured":"Kami\u0144ski, M., Lozin, V.: Coloring edges and vertices of graphs without short or long cycles. Contrib. Discrete Math. 2(1), 61\u201366 (2007). https:\/\/doi.org\/10.11575\/cdm.v2i1.61890","journal-title":"Contrib. Discrete Math."},{"key":"2756_CR3","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D Leven","year":"1983","unstructured":"Leven, D., Gail, Z.: NP completeness of finding the chromatic index of regular graphs. J. Algorithms 4, 35\u201344 (1983)","journal-title":"J. Algorithms"},{"issue":"4","key":"2756_CR4","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981). https:\/\/doi.org\/10.1137\/0210055","journal-title":"SIAM J. Comput."},{"key":"2756_CR5","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","volume":"57","author":"CT Ho\u00e0ng","year":"2010","unstructured":"Ho\u00e0ng, C.T., Kami\u0144ski, M., Lozin, V., Sawada, J., Shu, X.: Deciding $$k$$-colorability of $$P_5$$-free graphs in polynomial time. Algorithmica 57, 74\u201381 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9197-8","journal-title":"Algorithmica"},{"key":"2756_CR6","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring $$P_6$$-free graphs. I. Extending an excellent precoloring. Preprint arXiv:1802.02282 [math.CO] (2018)"},{"key":"2756_CR7","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring $$P_6$$-free graphs. II. Finding an excellent precoloring. Preprint arXiv:1802.02283 [math.CO] (2018)"},{"key":"2756_CR8","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring $$P_6$$-free graphs. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201919, pp. 1239\u20131256. Society for Industrial and Applied Mathematics, New York (2019)"},{"issue":"4","key":"2756_CR9","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1007\/s00493-017-3553-8","volume":"38","author":"F Bonomo","year":"2018","unstructured":"Bonomo, F., Chudnovsky, M., Maceli, P., Schaudt, O., Steinz, M., Zhong, M.: Three-coloring and list three-coloring of graphs without induced paths on seven vertices. Combinatorica 38(4), 779\u2013801 (2018). https:\/\/doi.org\/10.1007\/s00493-017-3553-8","journal-title":"Combinatorica"},{"key":"2756_CR10","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.ejc.2015.06.005","volume":"51","author":"S Huang","year":"2016","unstructured":"Huang, S.: Improved complexity results on $$k$$-coloring $$P_t$$-free graphs. Eur. J. Combin. 51, 336\u2013346 (2016). https:\/\/doi.org\/10.1016\/j.ejc.2015.06.005","journal-title":"Eur. J. Combin."},{"key":"2756_CR11","doi-asserted-by":"crossref","unstructured":"Cai, Q., Huang, S., Li, T., Shi, Y.: Vertex-critical $$(P_5, banner)$$-free graphs. In: Frontiers in Algorithmics\u201413th International Workshop. FAW 2019, Sanya, April 29\u2013May 3, 2019, Proceedings, vol. 11458, pp. 111\u2013120. Springer, Sanya (2019)","DOI":"10.1007\/978-3-030-18126-0_10"},{"key":"2756_CR12","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.dam.2014.06.007","volume":"182","author":"CT Ho\u00e0ng","year":"2015","unstructured":"Ho\u00e0ng, C.T., Moore, B., Recoskie, D., Sawada, J., Vatshelle, M.: Constructions of $$k$$-critical $$P_5$$-free graphs. Discrete Appl. Math. 182, 91\u201398 (2015). https:\/\/doi.org\/10.1016\/j.dam.2014.06.007","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"2756_CR13","doi-asserted-by":"publisher","first-page":"1682","DOI":"10.1137\/110829222","volume":"26","author":"F Maffray","year":"2012","unstructured":"Maffray, F., Morel, G.: On $$3$$-colorable $$P_5$$-free graphs. SIAM J. Discrete Math. 26(4), 1682\u20131708 (2012). https:\/\/doi.org\/10.1137\/110829222","journal-title":"SIAM J. Discrete Math."},{"key":"2756_CR14","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2021.02.029","volume":"864","author":"K Cameron","year":"2021","unstructured":"Cameron, K., Goedgebeur, J., Huang, S., Shi, Y.: $$k$$-critical graphs in $$P_5$$-free graphs. Theor. Comput. Sci. 864, 80\u201391 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.02.029","journal-title":"Theor. Comput. Sci."},{"key":"2756_CR15","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.dam.2023.07.014","volume":"341","author":"S Huang","year":"2023","unstructured":"Huang, S., Li, Z.: Vertex-critical $$(P_5, chair)$$-free graphs. Discrete Appl. Math. 341, 9\u201315 (2023). https:\/\/doi.org\/10.1016\/j.dam.2023.07.014","journal-title":"Discrete Appl. Math."},{"key":"2756_CR16","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.dam.2023.02.019","volume":"334","author":"S Huang","year":"2023","unstructured":"Huang, S., Li, J., Xia, W.: Critical ($$P_5$$, bull)-free graphs. Discrete Appl. Math. 334, 15\u201325 (2023). https:\/\/doi.org\/10.1016\/j.dam.2023.02.019","journal-title":"Discrete Appl. Math."},{"key":"2756_CR17","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.jctb.2019.04.006","volume":"140","author":"M Chudnovsky","year":"2020","unstructured":"Chudnovsky, M., Goedgebeur, J., Schaudt, O., Zhong, M.: Obstructions for three-coloring graphs without induced paths on six vertices. J. Combin. Ser. B 140, 45\u201383 (2020). https:\/\/doi.org\/10.1016\/j.jctb.2019.04.006","journal-title":"J. Combin. Ser. B"},{"issue":"1","key":"2756_CR18","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(1), 51\u2013229 (2006). https:\/\/doi.org\/10.4007\/annals.2006.164.51. arXiv:0212070 [math]","journal-title":"Ann. Math."},{"key":"2756_CR19","first-page":"264","volume":"s2\u201330","author":"FP Ramsey","year":"1928","unstructured":"Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. s2\u201330, 264\u2013286 (1928)","journal-title":"Proc. Lond. Math. Soc."},{"key":"2756_CR20","doi-asserted-by":"publisher","unstructured":"Cameron, B., Ho\u00e0ng, C.T., Sawada, J.: Dichotomizing $$k$$-vertex-critical $$H$$-free graphs for $$H$$ of order four. Discrete Appl. Math. 312, 106\u2013115 (2022) https:\/\/doi.org\/10.1016\/j.dam.2021.11.001 (ninth workshop on graph classes, optimization, and width parameters).","DOI":"10.1016\/j.dam.2021.11.001"},{"key":"2756_CR21","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.dam.2023.11.042","volume":"344","author":"T Abuadas","year":"2024","unstructured":"Abuadas, T., Cameron, B., Ho\u00e0ng, C.T., Sawada, J.: Vertex-critical $$(P_3+\\ell P_1)$$-free and vertex-critical (gem, co-gem)-free graphs. Discrete Appl. Math. 344, 179\u2013187 (2024). https:\/\/doi.org\/10.1016\/j.dam.2023.11.042","journal-title":"Discrete Appl. Math."},{"key":"2756_CR22","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.dam.2018.09.031","volume":"261","author":"M Kami\u0144ski","year":"2019","unstructured":"Kami\u0144ski, M., Pstrucha, A.: Certifying coloring algorithms for graphs without long induced paths. Discrete Appl. Math. 261, 258\u2013267 (2019). https:\/\/doi.org\/10.1016\/j.dam.2018.09.031","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"2756_CR23","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.ipl.2003.07.004","volume":"88","author":"V Lozin","year":"2003","unstructured":"Lozin, V., Rautenbach, D.: Some results on graphs without long induced paths. Inform. Process. Lett. 88(4), 167\u2013171 (2003). https:\/\/doi.org\/10.1016\/j.ipl.2003.07.004","journal-title":"Inform. Process. Lett."},{"key":"2756_CR24","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.dam.2022.05.014","volume":"320","author":"C Brause","year":"2022","unstructured":"Brause, C., Gei\u00dfer, M., Schiermeyer, I.: Homogeneous sets, clique-separators, critical graphs, and optimal $$\\chi $$-binding functions. Discrete Appl. Math. 320, 211\u2013222 (2022). https:\/\/doi.org\/10.1016\/j.dam.2022.05.014","journal-title":"Discrete Appl. Math."},{"key":"2756_CR25","doi-asserted-by":"crossref","unstructured":"Xia, W., Jooken, J., Goedgebeur, J., Huang, S.: Critical $$(P_5,dart)$$-free graphs. Preprint arXiv:2308.03414 [math.CO] (2023)","DOI":"10.1007\/978-3-031-49614-1_29"},{"key":"2756_CR26","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.dam.2016.05.018","volume":"216","author":"HS Dhaliwal","year":"2017","unstructured":"Dhaliwal, H.S., Hamel, A.M., Ho\u00e0ng, C.T., Maffray, F., McConnell, T.J.D., Panait, S.A.: On color-critical $$(P_5,$$co-$$P_5)$$-free graphs. Discrete Appl. Math. 216, 142\u2013148 (2017). https:\/\/doi.org\/10.1016\/j.dam.2016.05.018","journal-title":"Discrete Appl. Math."},{"key":"2756_CR27","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.dam.2023.03.008","volume":"334","author":"Q Cai","year":"2023","unstructured":"Cai, Q., Goedgebeur, J., Huang, S.: Some results on $$k$$-critical $$P_5$$-free graphs. Discrete Appl. Math. 334, 91\u2013100 (2023). https:\/\/doi.org\/10.1016\/j.dam.2023.03.008","journal-title":"Discrete Appl. Math."},{"key":"2756_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113936","volume":"961","author":"B Cameron","year":"2023","unstructured":"Cameron, B., Ho\u00e0ng, C.T.: A refinement on the structure of vertex-critical ($$P_5$$, gem)-free graphs. Theor. Comput. Sci. 961, 113936 (2023). https:\/\/doi.org\/10.1016\/j.tcs.2023.113936","journal-title":"Theor. Comput. Sci."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02756-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-024-02756-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-024-02756-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,27]],"date-time":"2024-04-27T18:03:29Z","timestamp":1714241009000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-024-02756-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,25]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["2756"],"URL":"https:\/\/doi.org\/10.1007\/s00373-024-02756-x","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,25]]},"assertion":[{"value":"4 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"30"}}