{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:01:59Z","timestamp":1786978919424,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031630200","type":"print"},{"value":"9783031630217","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-63021-7_23","type":"book-chapter","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T09:02:29Z","timestamp":1718960549000},"page":"301-313","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the\u00a0Finiteness of\u00a0k-Vertex-Critical $$2P_2$$-Free Graphs with\u00a0Forbidden Induced Squids or\u00a0Bulls"],"prefix":"10.1007","author":[{"given":"Melvin","family":"Adekanye","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christopher","family":"Bury","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1020-2883","authenticated-orcid":false,"given":"Ben","family":"Cameron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thaler","family":"Knodel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,6,22]]},"reference":[{"key":"23_CR1","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."},{"issue":"2","key":"23_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0095-8956(77)90037-5","volume":"23","author":"O Borodin","year":"1977","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. Ser. B 23(2), 247\u2013250 (1977). https:\/\/doi.org\/10.1016\/0095-8956(77)90037-5","journal-title":"J. Combin. Ser. B"},{"key":"23_CR3","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."},{"issue":"4","key":"23_CR4","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz, D.: New methods to color the vertices of a graph. Commun. ACM 22(4), 251\u2013256 (1979). https:\/\/doi.org\/10.1145\/359094.359101","journal-title":"Commun. ACM"},{"key":"23_CR5","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1007\/978-3-642-10631-6_61","volume-title":"Algorithms and Computation","author":"D Bruce","year":"2009","unstructured":"Bruce, D., Ho\u00e0ng, C.T., Sawada, J.: A certifying algorithm for 3-colorability of $$P_5$$-free graphs. In: Dong, Y., Du, D.Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 594\u2013604. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-10631-6_61"},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-030-18126-0_10","volume-title":"Frontiers in Algorithmics","author":"Q Cai","year":"2019","unstructured":"Cai, Q., Huang, S., Li, T., Shi, Y.: Vertex-critical ($$P_5$$, banner)-free graphs. In: Chen, Y., Deng, X., Lu, M. (eds.) FAW 2019. LNCS, vol. 11458, pp. 111\u2013120. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-18126-0_10"},{"key":"23_CR7","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":"23_CR8","unstructured":"Cameron, B.: P3P1free_critical (2021). https:\/\/github.com\/benrkcameron\/P3P1free_critical"},{"key":"23_CR9","unstructured":"Cameron, B.: 2P2bullfree (2023). https:\/\/github.com\/benrkcameron\/2P2bull"},{"key":"23_CR10","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"},{"key":"23_CR11","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. Theoret. Comput. Sci. 961, 113936 (2023). https:\/\/doi.org\/10.1016\/j.tcs.2023.113936","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR12","doi-asserted-by":"publisher","unstructured":"Cameron, B., Ho\u00e0ng, C.T.: Infinite families of $$k$$-vertex-critical $$({P}_5, {C}_5)$$-free graphs. Graphs Combin. 40(30) (2024). https:\/\/doi.org\/10.1007\/s00373-024-02756-x","DOI":"10.1007\/s00373-024-02756-x"},{"key":"23_CR13","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. Theoret. Comput. Sci. 864, 80\u201391 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2021.02.029","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"23_CR14","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","journal-title":"Ann. Math."},{"key":"23_CR15","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"},{"key":"23_CR16","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring $$P_6$$-free graphs. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pp. 1239\u20131256. Society for Industrial and Applied Mathematics, USA (2019)"},{"key":"23_CR17","doi-asserted-by":"publisher","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring $$P_6$$-free graphs. I. Extending an excellent precoloring. SIAM J. Comput. 53(1), 111\u2013145 (2024). https:\/\/doi.org\/10.1137\/18M1234837","DOI":"10.1137\/18M1234837"},{"key":"23_CR18","doi-asserted-by":"publisher","unstructured":"Chudnovsky, M., Spirkl, S., Zhong, M.: Four-coloring $$P_6$$-free graphs. II. Finding an excellent precoloring. SIAM J. Comput. 53(1), 146\u2013187 (2024). https:\/\/doi.org\/10.1137\/18M1234849","DOI":"10.1137\/18M1234849"},{"issue":"4","key":"23_CR19","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1002\/jgt.22845","volume":"101","author":"DW Cranston","year":"2022","unstructured":"Cranston, D.W., Lafayette, H., Rabern, L.: Coloring $$(P_5,$$gem$$)$$-free graphs with $$\\Delta -1$$ colors. J. Graph Theory 101(4), 633\u2013642 (2022). https:\/\/doi.org\/10.1002\/jgt.22845","journal-title":"J. Graph Theory"},{"key":"23_CR20","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."},{"issue":"1","key":"23_CR21","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1007\/s12190-020-01419-3","volume":"65","author":"UK Gupta","year":"2021","unstructured":"Gupta, U.K., Pradhan, D.: Borodin-Kostochka\u2019s conjecture on $$({P}_5,{C}_4)$$-free graphs. J. Appl. Math. Comput. 65(1), 877\u2013884 (2021). https:\/\/doi.org\/10.1007\/s12190-020-01419-3","journal-title":"J. Appl. Math. Comput."},{"issue":"1","key":"23_CR22","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"MM Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: A still better performance guarantee for approximate graph coloring. Inform. Process. Lett. 45(1), 19\u201323 (1993). https:\/\/doi.org\/10.1016\/0020-0190(93)90246-6","journal-title":"Inform. Process. Lett."},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s00373-023-02696-y","volume":"39","author":"P Haxell","year":"2023","unstructured":"Haxell, P., Naserasr, R.: A note on $$\\Delta $$-critical graphs. Graphs Combin. 39, 101 (2023). https:\/\/doi.org\/10.1007\/s00373-023-02696-y","journal-title":"Graphs Combin."},{"key":"23_CR24","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":"23_CR25","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":"23_CR26","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":"23_CR27","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. European J. Combin. 51, 336\u2013346 (2016). https:\/\/doi.org\/10.1016\/j.ejc.2015.06.005","journal-title":"European J. Combin."},{"key":"23_CR28","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":"23_CR29","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":"23_CR30","doi-asserted-by":"publisher","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","DOI":"10.11575\/cdm.v2i1.61890"},{"key":"23_CR31","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."},{"key":"23_CR32","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"23_CR33","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":"23_CR34","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":"23_CR35","doi-asserted-by":"crossref","unstructured":"Wu, D., Wu, R.: Borodin-Kostochka conjecture for a class of $$P_6$$-free graphs. preprint, arXiv: arXiv:2306.12062 (2023)","DOI":"10.2139\/ssrn.4503372"},{"key":"23_CR36","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/978-3-031-49614-1_29","volume-title":"COCOA 2023, Part II","author":"W Xia","year":"2023","unstructured":"Xia, W., Jooken, J., Goedgebeur, J., Huang, S.: Critical $$(P_5, dart)$$-free graphs. In: Wu, W., Guo, J. (eds.) COCOA 2023, Part II. LNCS, vol. 14462, pp. 390\u2013402. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-49614-1_29"},{"key":"23_CR37","doi-asserted-by":"crossref","unstructured":"Xia, W., Jooken, J., Goedgebeur, J., Huang, S.: Some Results on Critical ($$P_5,H$$)-free Graphs. preprint, arXiv: arXiv:2403.05611 (2024)","DOI":"10.1007\/978-3-031-49614-1_29"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-63021-7_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T09:15:54Z","timestamp":1718961354000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-63021-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031630200","9783031630217"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-63021-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"22 June 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ischia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"35","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2024.di.unisa.it","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}