{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T16:02:36Z","timestamp":1781625756639,"version":"3.54.5"},"reference-count":35,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100004281","name":"National Science Centre Poland","doi-asserted-by":"publisher","award":["2021\/41\/N\/ST6\/01507"],"award-info":[{"award-number":["2021\/41\/N\/ST6\/01507"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"National Science Centre Poland","doi-asserted-by":"publisher","award":["2018\/31\/D\/ST6\/00062"],"award-info":[{"award-number":["2018\/31\/D\/ST6\/00062"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003130","name":"Research Foundation Flanders","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\/501100004040","name":"KU Leuven","doi-asserted-by":"publisher","award":["G0AGX24N"],"award-info":[{"award-number":["G0AGX24N"]}],"id":[{"id":"10.13039\/501100004040","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2026,5]]},"DOI":"10.1016\/j.ic.2026.105445","type":"journal-article","created":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T07:52:00Z","timestamp":1774338720000},"page":"105445","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Minimal obstructions to C5-coloring in hereditary graph classes"],"prefix":"10.1016","volume":"310","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8984-2463","authenticated-orcid":false,"given":"Jan","family":"Goedgebeur","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5256-1921","authenticated-orcid":false,"given":"Jorik","family":"Jooken","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1414-3507","authenticated-orcid":false,"given":"Karolina","family":"Okrasa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":false,"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6817-0976","authenticated-orcid":false,"given":"Oliver","family":"Schaudt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2026.105445_bib0001","series-title":"49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)","article-title":"Minimal obstructions to C5-coloring in hereditary graph classes","author":"Goedgebeur","year":"2024"},{"issue":"2","key":"10.1016\/j.ic.2026.105445_bib0002","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid method and its consequences in combinatorial optimization","volume":"1","author":"Gr\u00f6tschel","year":"1981","journal-title":"Combinatorics"},{"issue":"4","key":"10.1016\/j.ic.2026.105445_bib0003","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/BF02579139","article-title":"Corrigendum to our paper \u201cthe ellipsoid method and its consequences in combinatorial optimization\u201d","volume":"4","author":"Gr\u00f6tschel","year":"1984","journal-title":"Combinatorics"},{"issue":"1","key":"10.1016\/j.ic.2026.105445_bib0004","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","article-title":"Linear time algorithms for NP-hard problems restricted to partial k-trees","volume":"23","author":"Arnborg","year":"1989","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"10.1016\/j.ic.2026.105445_bib0005","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0601025","article-title":"The complexity of coloring circular arcs and chords","volume":"1","author":"Garey","year":"1980","journal-title":"SIAM J. Algebraic Discret. Methods"},{"issue":"4","key":"10.1016\/j.ic.2026.105445_bib0006","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1017\/S0963548398003678","article-title":"Uniquely colourable graphs and the hardness of colouring graphs of large girth","volume":"7","author":"Emden-Weinert","year":"1998","journal-title":"Comb. Probab. Comput."},{"key":"10.1016\/j.ic.2026.105445_bib0007","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."},{"issue":"1","key":"10.1016\/j.ic.2026.105445_bib0008","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.ic.2026.105445_bib0009","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":"Eur. J. Comb."},{"key":"10.1016\/j.ic.2026.105445_bib0010","series-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January \u20139, 2019","first-page":"1239","article-title":"Four-coloring P6-free graphs","author":"Spirkl","year":"2019"},{"issue":"4","key":"10.1016\/j.ic.2026.105445_bib0011","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1007\/s00493-017-3553-8","article-title":"Three-coloring and list three-coloring of graphs without induced paths on seven vertices","volume":"38","author":"Bonomo","year":"2018","journal-title":"Combinatorics"},{"issue":"1","key":"10.1016\/j.ic.2026.105445_bib0012","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.ic.2026.105445_bib0013","series-title":"4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11\u201312, 2021","first-page":"204","article-title":"Quasi-polynomial-time algorithm for independent set in Pt-free graphs via shrinking the space of induced paths","author":"Pilipczuk","year":"2021"},{"issue":"7","key":"10.1016\/j.ic.2026.105445_bib0014","doi-asserted-by":"crossref","first-page":"1833","DOI":"10.1007\/s00453-020-00675-w","article-title":"Colouring (Pr+Ps)-free graphs","volume":"82","author":"Klimo\u0161ov\u00e1","year":"2020","journal-title":"Algorithmica"},{"issue":"1","key":"10.1016\/j.ic.2026.105445_bib0015","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/s00453-020-00754-y","article-title":"List 3-coloring graphs with no induced P6+rP3","volume":"83","author":"Chudnovsky","year":"2021","journal-title":"Algorithmica"},{"issue":"2","key":"10.1016\/j.ic.2026.105445_bib0016","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.ic.2026.105445_bib0017","series-title":"Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16\u201318, 2009. Proceedings","first-page":"594","article-title":"A certifying algorithm for 3-colorability of P5-free graphs","volume":"5878","author":"Bruce","year":"2009"},{"key":"10.1016\/j.ic.2026.105445_bib0018","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.jctb.2019.04.006","article-title":"Obstructions for three-coloring graphs without induced paths on six vertices","volume":"140","author":"Chudnovsky","year":"2020","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.ic.2026.105445_bib0019","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":"Discret. Appl. Math."},{"issue":"1","key":"10.1016\/j.ic.2026.105445_bib0020","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","article-title":"On the complexity of H-coloring","volume":"48","author":"Hell","year":"1990","journal-title":"J. Comb. Theory, Ser. B"},{"key":"10.1016\/j.ic.2026.105445_bib0021","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2023.105015","article-title":"Complexity of Ck-coloring in hereditary classes of graphs","volume":"292","author":"Chudnovsky","year":"2023","journal-title":"Inf. Comput."},{"key":"10.1016\/j.ic.2026.105445_bib0022","unstructured":"T. Feder, P. Hell, Edge list homomorphisms, (Unpublished manuscript, available at http:\/\/theory.stanford.edu\/~tomas\/edgelist.ps)."},{"key":"10.1016\/j.ic.2026.105445_bib0023","series-title":"33rd International Symposium on Algorithms and Computation (ISAAC 2022)","first-page":"14:1","article-title":"Computing homomorphisms in hereditary graph classes: the peculiar case of the 5-wheel and graphs with no long claws","volume":"248","author":"D\u0119bski","year":"2022"},{"key":"10.1016\/j.ic.2026.105445_bib0024","series-title":"38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16\u201319, 2021, Saarbrcken, Germany (Virtual Conference)","first-page":"54:1","article-title":"Complexity of the list homomorphism problem in hereditary graph classes","volume":"187","author":"Okrasa","year":"2021"},{"issue":"2","key":"10.1016\/j.ic.2026.105445_bib0025","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1002\/jgt.20017","article-title":"Note on projective graphs","volume":"47","author":"\u0141uczak","year":"2004","journal-title":"J. Graph Theory"},{"issue":"13","key":"10.1016\/j.ic.2026.105445_bib0026","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0012-365X(92)90282-K","article-title":"The core of a graph","volume":"109","author":"Hell","year":"1992","journal-title":"Discret. Math."},{"key":"10.1016\/j.ic.2026.105445_bib0027","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":"Discret. Appl. Math."},{"issue":"2","key":"10.1016\/j.ic.2026.105445_bib0028","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.ic.2026.105445_bib0029","unstructured":"Source code of algorithm Expand, 2024, (https:\/\/github.com\/JorikJooken\/ObstructionsForC5Coloring)."},{"key":"10.1016\/j.ic.2026.105445_bib0030","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":"Discret. Appl. Math."},{"key":"10.1016\/j.ic.2026.105445_bib0031","series-title":"Handbook of product graphs","author":"Hammack","year":"2011"},{"key":"10.1016\/j.ic.2026.105445_bib0032","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","article-title":"Practical graph isomorphism, II","volume":"60","author":"McKay","year":"2014","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.ic.2026.105445_bib0033","series-title":"Combinatorial Optimization and Applications - 17th International Conference, COCOA 2023, Hawaii, HI, USA, December 15\u201317, 2023, Proceedings, Part II","first-page":"390","article-title":"Critical (P5, dart)-free graphs","volume":"14462","author":"Xia","year":"2023"},{"key":"10.1016\/j.ic.2026.105445_bib0034","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":"Discret. Appl. Math."},{"key":"10.1016\/j.ic.2026.105445_bib0035","article-title":"Some results on critical (P5, H)-free graphs","author":"Xia","year":"2024","journal-title":"CoRR"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000428?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540126000428?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T14:53:43Z","timestamp":1781621623000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540126000428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":35,"alternative-id":["S0890540126000428"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2026.105445","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2026,5]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Minimal obstructions to C5-coloring in hereditary graph classes","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ic.2026.105445","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"105445"}}