{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T08:12:02Z","timestamp":1778746322815,"version":"3.51.4"},"reference-count":36,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T00:00:00Z","timestamp":1780272000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100003130","name":"FWO","doi-asserted-by":"publisher","award":["1222524N"],"award-info":[{"award-number":["1222524N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003130","name":"FWO","doi-asserted-by":"publisher","award":["G0AGX24N"],"award-info":[{"award-number":["G0AGX24N"]}],"id":[{"id":"10.13039\/501100003130","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-2025-00001"],"award-info":[{"award-number":["DGECR-2025-00001"]}],"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-2025-06012"],"award-info":[{"award-number":["RGPIN-2025-06012"]}],"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-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\/501100004040","name":"KU Leuven","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004040","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12311530678"],"award-info":[{"award-number":["12311530678"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12171256"],"award-info":[{"award-number":["12171256"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12161141006"],"award-info":[{"award-number":["12161141006"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["VS01224N"],"award-info":[{"award-number":["VS01224N"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1016\/j.tcs.2026.115934","type":"journal-article","created":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T06:47:59Z","timestamp":1774939679000},"page":"115934","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Vertex-critical (P5, W4)-free graphs"],"prefix":"10.1016","volume":"1075","author":[{"given":"Wen","family":"Xia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jorik","family":"Jooken","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Goedgebeur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iain","family":"Beaton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ben","family":"Cameron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shenwei","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2026.115934_bib0001","series-title":"31st International Conference on Computing and Combinatorics, COCOON","first-page":"1","article-title":"Vertex-critical (P5, W4)-free graphs","author":"Xia","year":"2025"},{"key":"10.1016\/j.tcs.2026.115934_bib0002","series-title":"Proceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory, and Computing. Congress. Numer., VIII","first-page":"3","article-title":"Coverings and coloring of hypergraphs","author":"Lov\u00e1sz","year":"1973"},{"key":"10.1016\/j.tcs.2026.115934_bib0003","series-title":"Complexity of Computer Computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heigts, N.Y., 1972)","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/j.tcs.2026.115934_bib0004","first-page":"61","article-title":"Coloring edges and vertices of graphs without short or long cycles","volume":"2","author":"Kami\u0144ski","year":"2007","journal-title":"Contrib. Discrete Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0005","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","article-title":"The NP-completeness of edge-coloring","volume":"10","author":"Holyer","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.tcs.2026.115934_bib0006","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","article-title":"NP completeness of finding the chromatic index of regular graphs","volume":"4","author":"Leven","year":"1983","journal-title":"J. Algorithms"},{"key":"10.1016\/j.tcs.2026.115934_bib0007","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/s00453-008-9197-8","article-title":"Deciding k-colorability of P5-free graphs in polynomial time","volume":"57","author":"Ho\u00e0ng","year":"2010","journal-title":"Algorithmica"},{"key":"10.1016\/j.tcs.2026.115934_bib0008","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1016\/j.ejc.2015.06.005","article-title":"Improved complexity results on k-coloring Pt-free graphs","volume":"51","author":"Huang","year":"2016","journal-title":"European J. Combin."},{"issue":"2","key":"10.1016\/j.tcs.2026.115934_bib0009","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.cosrev.2010.09.009","article-title":"Certifying algorithms","volume":"5","author":"Mcconnell","year":"2011","journal-title":"Comput. Sci. Rev."},{"key":"10.1016\/j.tcs.2026.115934_bib0010","doi-asserted-by":"crossref","unstructured":"Q. Cai, S. Huang, T. Li, Y. Shi, Vertex-critical (P5,banner)-free graph, Frontiers in Algorithmics -13th International Workshop, FAW 2019 11458 (2019) 111\u2013120.","DOI":"10.1007\/978-3-030-18126-0_10"},{"key":"10.1016\/j.tcs.2026.115934_bib0011","doi-asserted-by":"crossref","unstructured":"D. Bruce, C.T. Ho\u00e0ng, J. Sawada, A certifying algorithm for 3-colorability of P5-free graphs, Proceedings of 20th International Symposium on Algorithms and Computation 5878 (2009) 594\u2013604.","DOI":"10.1007\/978-3-642-10631-6_61"},{"key":"10.1016\/j.tcs.2026.115934_bib0012","doi-asserted-by":"crossref","first-page":"1682","DOI":"10.1137\/110829222","article-title":"On 3-colorable P5-free graphs","volume":"26","author":"Maffray","year":"2012","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0013","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.dam.2014.06.007","article-title":"Constructions of k-critical P5-free graphs","volume":"182","author":"Ho\u00e0ng","year":"2015","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0014","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/j.tcs.2021.02.029","article-title":"k-critical graphs in P5-free graphs","volume":"864","author":"Cameron","year":"2021","journal-title":"Theoret. Comput. Sci"},{"key":"10.1016\/j.tcs.2026.115934_bib0015","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/s00373-024-02756-x","article-title":"Infinite families of k-vertex-critical (P5, C5)-graphs","volume":"40","author":"Cameron","year":"2024","journal-title":"Graphs Combin."},{"key":"10.1016\/j.tcs.2026.115934_bib0016","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.dam.2023.02.019","article-title":"Critical (P5, bull)-free graphs","volume":"334","author":"Huang","year":"2023","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0017","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.dam.2023.07.014","article-title":"Vertex-critical (P5, chair)-free graphs","volume":"341","author":"Huang","year":"2023","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0018","series-title":"16th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2023","first-page":"390","article-title":"Critical (P5, dart)-free graphs","author":"Xia","year":"2024"},{"key":"10.1016\/j.tcs.2026.115934_bib0019","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.dam.2022.05.014","article-title":"Homogeneous sets, clique-separators, critical graphs and optimal \u03c7-binding functions","volume":"320","author":"Brause","year":"2022","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0020","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/j.dam.2021.11.001","article-title":"Dichotomizing k-vertex-critical H-free graphs for H of order four","volume":"312","author":"Cameron","year":"2022","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0021","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.dam.2023.11.042","article-title":"Vertex-critical P3+\u2113P1-free and vertex-critical (gem, co-gem)-free graphs","volume":"344","author":"Abuadas","year":"2024","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0022","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.dam.2023.03.008","article-title":"Some results on k-critical P5-free graphs","volume":"334","author":"Cai","year":"2023","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0023","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/j.dam.2018.09.031","article-title":"Certifying coloring algorithms for graphs without long induced paths","volume":"261","author":"Kami\u0144ski","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0024","series-title":"30th International Conference on Computing and Combinatorics, COCOON","article-title":"Some results on critical (P5, H)-free graphs","author":"Xia","year":"2024"},{"key":"10.1016\/j.tcs.2026.115934_bib0025","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/j.dam.2016.05.018","article-title":"On color-critical (P5, co-P5)-free graphs","volume":"216","author":"Dhaliwal","year":"2017","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0026","series-title":"Graph Theory","author":"Bondy","year":"2008"},{"key":"10.1016\/j.tcs.2026.115934_bib0027","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/S0166-218X(99)00012-8","article-title":"On minimal imperfect graphs without induced P5","volume":"94","author":"Barr\u00e9","year":"1999","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0028","doi-asserted-by":"crossref","first-page":"51","DOI":"10.4007\/annals.2006.164.51","article-title":"The strong perfect graph theorem","volume":"164","author":"Chudnovsky","year":"2006","journal-title":"Ann. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0029","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1002\/jgt.22151","article-title":"Exhaustive generation of k-critical H-free graphs","volume":"87","author":"Goedgebeur","year":"2018","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.tcs.2026.115934_bib0030","series-title":"49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), Volume 306 of LIPIcs","first-page":"1","article-title":"Minimal obstructions to C5-coloring in hereditary graph classes","author":"Goedgebeur","year":"2024"},{"key":"10.1016\/j.tcs.2026.115934_bib0031","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical graph isomorphism","volume":"60","author":"Mckay","year":"2014","journal-title":"II. J. Symbolic Comput."},{"key":"10.1016\/j.tcs.2026.115934_bib0032","series-title":"Homepage of generator for k-critical H-free graphs","author":"Goedgebeur","year":"2026"},{"key":"10.1016\/j.tcs.2026.115934_bib0033","series-title":"GitHub page containing generator for k-vertex-critical H-free graphs","author":"Jooken","year":"2026"},{"key":"10.1016\/j.tcs.2026.115934_bib0034","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.dam.2022.10.013","article-title":"House of graphs 2.0: a database of interesting graphs and more","volume":"325","author":"Coolsaet","year":"2023","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.tcs.2026.115934_bib0035","doi-asserted-by":"crossref","DOI":"10.1016\/j.tcs.2025.115234","article-title":"Vertex-critical graphs in co-gem-free graphs","volume":"1042","author":"Beaton","year":"2025","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115934_bib0036","first-page":"301","article-title":"On the finiteness of k-Vertex-Critical 2P2-Free graphs with forbidden induced squids or bulls","volume":"14764","author":"Adekanye","year":"2024","journal-title":"Adele Anna Rescigno and Ugo Vaccaro editors, 35th International Workshop on Combinatorial Algorithms. IWOCA 2024"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526001933?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526001933?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T07:37:49Z","timestamp":1778744269000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526001933"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6]]},"references-count":36,"alternative-id":["S0304397526001933"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115934","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,6]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Vertex-critical (P5, W4)-free graphs","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115934","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"115934"}}