{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:59:02Z","timestamp":1780783142955,"version":"3.54.1"},"publisher-location":"Cham","reference-count":43,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-27732-9_9","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:13:51Z","timestamp":1780780431000},"page":"118-130","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Vertex-Critical Graphs in\u00a0Subfamilies of\u00a0$$(P_4+\\ell P_1)$$-Free Graphs"],"prefix":"10.1007","author":[{"given":"Iain","family":"Beaton","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ben","family":"Cameron","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"key":"9_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."},{"key":"9_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2025.115234","volume":"1042","author":"I Beaton","year":"2025","unstructured":"Beaton, I., Cameron, B.: Vertex-critical graphs in co-gem-free graphs. Theoret. Comput. Sci. 1042, 115234 (2025). https:\/\/doi.org\/10.1016\/j.tcs.2025.115234","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"9_CR4","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":"9_CR5","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":"9_CR6","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":"9_CR7","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.dam.2021.11.001","volume":"312","author":"B Cameron","year":"2022","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","journal-title":"Discrete Appl. Math."},{"key":"9_CR8","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":"9_CR9","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/s00373-024-02756-x","volume":"40","author":"B Cameron","year":"2024","unstructured":"Cameron, B., Ho\u00e0ng, C.T.: Infinite families of $$k$$-vertex-critical $$({P}_5, {C}_5)$$-free graphs. Graphs Combin. 40, 30 (2024)","journal-title":"Graphs Combin."},{"key":"9_CR10","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."},{"key":"9_CR11","unstructured":"Chen, R., Wu, D., Zhang, X.: Structure, perfect divisibility and coloring of $$(P_2\\cup P4, C_3)$$-free graphs. preprint, arXiv:2509.14135 [math.CO] (2025)"},{"issue":"1","key":"9_CR12","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/18M1210290","volume":"34","author":"M Chudnovsky","year":"2020","unstructured":"Chudnovsky, M., Goedgebeur, J., Schaudt, O., Zhong, M.: Obstructions for three-coloring and list three-coloring $$H$$-free graphs. SIAM J. Discrete Math. 34(1), 431\u2013469 (2020)","journal-title":"SIAM J. Discrete Math."},{"issue":"5","key":"9_CR13","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1007\/s00493-024-00106-2","volume":"44","author":"M Chudnovsky","year":"2024","unstructured":"Chudnovsky, M., Hajebi, S., Spirkl, S.: List-$$k$$-Coloring $$H$$-Free Graphs for All $$k>4$$. Combinatorica 44(5), 1063\u20131068 (2024). https:\/\/doi.org\/10.1007\/s00493-024-00106-2","journal-title":"Combinatorica"},{"issue":"1","key":"9_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":"9_CR15","doi-asserted-by":"crossref","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":"9_CR16","doi-asserted-by":"crossref","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":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s00453-013-9777-0","volume":"71","author":"JF Couturier","year":"2015","unstructured":"Couturier, J.F., Golovach, P.A., Kratsch, D., Paulusma, D.: List coloring in the absence of a linear forest. Algorithmica 71(1), 21\u201335 (2015). https:\/\/doi.org\/10.1007\/s00453-013-9777-0","journal-title":"Algorithmica"},{"key":"9_CR18","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":"9_CR19","doi-asserted-by":"publisher","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), 285\u2013290 (2003). https:\/\/doi.org\/10.1016\/S0012-365X(03)00197-3. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0012365X03001973","DOI":"10.1016\/S0012-365X(03)00197-3"},{"issue":"3","key":"9_CR20","doi-asserted-by":"publisher","first-page":"2004","DOI":"10.1137\/21M1443352","volume":"36","author":"S Hajebi","year":"2022","unstructured":"Hajebi, S., Li, Y., Spirkl, S.: Complexity dichotomy for list-5-coloring with a forbidden induced subgraph. SIAM J. Discrete Math. 36(3), 2004\u20132027 (2022). https:\/\/doi.org\/10.1137\/21M1443352","journal-title":"SIAM J. Discrete Math."},{"key":"9_CR21","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":"9_CR22","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":"9_CR23","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":"9_CR24","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":"9_CR25","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":"9_CR26","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":"9_CR27","doi-asserted-by":"crossref","unstructured":"Jua, Y., Jooken, J., Goedgebeur, J., Huang, S.: There are finitely many 5-vertex-critical ($$P_6$$, bull)-free graphs [math.CO] (2025)","DOI":"10.1002\/jgt.70027"},{"key":"9_CR28","doi-asserted-by":"crossref","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.55016\/ojs\/cdm.v2i1.61890"},{"key":"9_CR29","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":"9_CR30","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":"9_CR31","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":"9_CR32","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."},{"issue":"2","key":"9_CR33","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.cosrev.2010.09.009","volume":"5","author":"R McConnell","year":"2011","unstructured":"McConnell, R., Mehlhorn, K., N\u00e4her, S., Schweitzer, P.: Certifying algorithms. Comput. Sci. Rev. 5(2), 119\u2013161 (2011). https:\/\/doi.org\/10.1016\/j.cosrev.2010.09.009","journal-title":"Comput. Sci. Rev."},{"issue":"5","key":"9_CR34","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1016\/j.disc.2012.10.019","volume":"313","author":"AV Pyatkin","year":"2013","unstructured":"Pyatkin, A.V.: Triangle-free $$2P_3$$-free graphs are $$4$$-colorable. Discret. Math. 313(5), 715\u2013720 (2013). https:\/\/doi.org\/10.1016\/j.disc.2012.10.019","journal-title":"Discret. Math."},{"key":"9_CR35","doi-asserted-by":"crossref","unstructured":"Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. (s2\u201330), 264\u2013286 (1928)","DOI":"10.1112\/plms\/s2-30.1.264"},{"issue":"1","key":"9_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-003-0540-1","volume":"20","author":"B Randerath","year":"2004","unstructured":"Randerath, B., Schiermeyer, I.: Vertex colouring and forbidden subgraphs\u2013a survey. Graphs Combin. 20(1), 1\u201340 (2004). https:\/\/doi.org\/10.1007\/s00373-003-0540-1","journal-title":"Graphs Combin."},{"issue":"1","key":"9_CR37","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/BF01171114","volume":"27","author":"E Sperner","year":"1928","unstructured":"Sperner, E.: Ein Satz \u00fcber Untermengen einer endlichen Menge. Math. Z. 27(1), 544\u2013548 (1928). https:\/\/doi.org\/10.1007\/BF01171114","journal-title":"Math. Z."},{"issue":"2","key":"9_CR38","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":"9_CR39","volume-title":"Introduction to Graph Theory","author":"DB West","year":"1996","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall Inc, Upper Saddle River (1996)"},{"key":"9_CR40","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/978-981-95-0218-9_11","volume-title":"Computing and Combinatorics","author":"W Xia","year":"2026","unstructured":"Xia, W., Jooken, J., Goedgebeur, J., Beaton, I., Cameron, B., Huang, S.: Vertex-critical $$(P_5, W_4)$$-free graphs. In: Fomin, F.V., Xiao, M. (eds.) Computing and Combinatorics, pp. 139\u2013152. Springer, Singapore (2026)"},{"key":"9_CR41","doi-asserted-by":"crossref","unstructured":"Xia, W., Jooken, J., Goedgebeur, J., Huang, S.: Critical $$(P_5, dart)$$-free graphs. In: Combinatorial Optimization and Applications: 16th International Conference, COCOA 2023, Hawaii, HI, USA, 15\u201317 December 2023, Proceedings, Part II, pp. 390\u2013402. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-49614-1_29","DOI":"10.1007\/978-3-031-49614-1_29"},{"key":"9_CR42","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2025.115411","volume":"1051","author":"W Xia","year":"2025","unstructured":"Xia, W., Jooken, J., Goedgebeur, J., Huang, S.: Some results on critical $$(P_5, H)$$-free graphs. Theoret. Comput. Sci. 1051, 115411 (2025). https:\/\/doi.org\/10.1016\/j.tcs.2025.115411","journal-title":"Theoret. Comput. Sci."},{"key":"9_CR43","unstructured":"Zhou, Y., Jooken, J., Shan, B., Goedgebeur, J., Huang, S.: Three-coloring triangle-free graphs without long forbidden paths [math.CO] (2025)"}],"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-032-27732-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:13:55Z","timestamp":1780780435000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"7 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The author(s) 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":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}