{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,19]],"date-time":"2026-09-19T17:03:54Z","timestamp":1789837434755,"version":"4.0.1"},"reference-count":37,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,12,1]],"date-time":"2026-12-01T00:00:00Z","timestamp":1796083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,12,1]],"date-time":"2026-12-01T00:00:00Z","timestamp":1796083200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T00:00:00Z","timestamp":1784592000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100010446","name":"Institute for Basic Science","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100010446","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["European Journal of Combinatorics"],"published-print":{"date-parts":[[2026,12]]},"DOI":"10.1016\/j.ejc.2026.104430","type":"journal-article","created":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T16:46:44Z","timestamp":1785516404000},"page":"104430","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Twin-width VIIIa: Delineation"],"prefix":"10.1016","volume":"138","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dibyayan","family":"Chakraborty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noleen","family":"K\u00f6hler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raul","family":"Lopes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"issue":"2","key":"10.1016\/j.ejc.2026.104430_b1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in a k-tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM J. Algebraic Discret. Methods"},{"issue":"3","key":"10.1016\/j.ejc.2026.104430_b2","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1305\/ndjfl\/1093870870","article-title":"Second-order quantifiers and the complexity of theories.","volume":"26","author":"Baldwin","year":"1985","journal-title":"Notre Dame J. Form. Log."},{"key":"10.1016\/j.ejc.2026.104430_b3","series-title":"49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France","first-page":"18:1","article-title":"Deciding twin-width at most 4 is NP-complete","volume":"229","author":"Berg\u00e9","year":"2022"},{"issue":"6","key":"10.1016\/j.ejc.2026.104430_b4","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A linear-time algorithm for finding tree-decompositions of small treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ejc.2026.104430_b5","series-title":"17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany","first-page":"9:1","article-title":"Twin-width VIII: delineation and win-wins","volume":"vol. 249","author":"Bonnet","year":"2022"},{"key":"10.1016\/j.ejc.2026.104430_b6","series-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms","first-page":"1977","article-title":"Twin-width II: small classes","author":"Bonnet","year":"2021"},{"issue":"3","key":"10.1016\/j.ejc.2026.104430_b7","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1145\/3651151","article-title":"Twin-width IV: ordered graphs and matrices","volume":"71","author":"Bonnet","year":"2024","journal-title":"J. ACM"},{"issue":"1","key":"10.1016\/j.ejc.2026.104430_b8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3486655","article-title":"Twin-width I: Tractable FO Model Checking","volume":"69","author":"Bonnet","year":"2022","journal-title":"J. ACM"},{"issue":"3","key":"10.1016\/j.ejc.2026.104430_b9","article-title":"Twin-width and permutations","volume":"20","author":"Bonnet","year":"2024","journal-title":"Log. Methods Comput. Sci."},{"issue":"3","key":"10.1016\/j.ejc.2026.104430_b10","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","article-title":"Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms","volume":"13","author":"Booth","year":"1976","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"10.1016\/j.ejc.2026.104430_b11","article-title":"On first-order transductions of classes of graphs","volume":"21","author":"Braunfeld","year":"2025","journal-title":"Log. Methods Comput. Sci."},{"issue":"1","key":"10.1016\/j.ejc.2026.104430_b12","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The monadic second-order logic of graphs. I. Recognizable sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inform. and Comput."},{"issue":"2","key":"10.1016\/j.ejc.2026.104430_b13","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","article-title":"Linear time solvable optimization problems on graphs of bounded clique-width","volume":"33","author":"Courcelle","year":"2000","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.ejc.2026.104430_b14","series-title":"First Conference of the Centre for Discrete Mathematics and Theoretical Computer Science, DMTCS 1996, Auckland, New Zealand, December, 9-13, 1996","first-page":"194","article-title":"The parameterized complexity of relational database queries and an improved characterization of W[1]","author":"Downey","year":"1996"},{"key":"10.1016\/j.ejc.2026.104430_b15","series-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024","first-page":"1550","article-title":"Flip-breakability: A combinatorial dichotomy for monadically dependent graph classes","author":"Dreier","year":"2024"},{"issue":"5","key":"10.1016\/j.ejc.2026.104430_b16","doi-asserted-by":"crossref","first-page":"36:1","DOI":"10.1145\/2499483","article-title":"Testing first-order properties for subclasses of sparse graphs","volume":"60","author":"Dvor\u00e1k","year":"2013","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.ejc.2026.104430_b17","doi-asserted-by":"crossref","first-page":"11:1","DOI":"10.1145\/3360011","article-title":"Model-checking on ordered structures","volume":"21","author":"Eickmeyer","year":"2020","journal-title":"ACM Trans. Comput. Log."},{"key":"10.1016\/j.ejc.2026.104430_b18","series-title":"Classic Papers in Combinatorics","first-page":"49","article-title":"A combinatorial problem in geometry","author":"Erd\u0151s","year":"1987"},{"issue":"2","key":"10.1016\/j.ejc.2026.104430_b19","doi-asserted-by":"crossref","first-page":"909","DOI":"10.1137\/070687256","article-title":"Clique-width is NP-complete","volume":"23","author":"Fellows","year":"2009","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"10.1016\/j.ejc.2026.104430_b20","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1137\/S0097539799360768","article-title":"Fixed-parameter tractability, definability, and model-checking","volume":"31","author":"Flum","year":"2001","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ejc.2026.104430_b21","series-title":"IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015","first-page":"963","article-title":"FO model checking on posets of bounded width","author":"Gajarsk\u00fd","year":"2015"},{"issue":"4","key":"10.1016\/j.ejc.2026.104430_b22","doi-asserted-by":"crossref","first-page":"28:1","DOI":"10.1145\/3383206","article-title":"A new perspective on FO model checking of dense graph classes","volume":"21","author":"Gajarsk\u00fd","year":"2020","journal-title":"ACM Trans. Comput. Log."},{"issue":"4","key":"10.1016\/j.ejc.2026.104430_b23","article-title":"Faster existential FO model checking on posets","volume":"11","author":"Gajarsk\u00fd","year":"2015","journal-title":"Log. Methods Comput. Sci."},{"issue":"4","key":"10.1016\/j.ejc.2026.104430_b24","doi-asserted-by":"crossref","first-page":"29:1","DOI":"10.1145\/3382093","article-title":"First-order interpretations of bounded expansion classes","volume":"21","author":"Gajarsk\u00fd","year":"2020","journal-title":"ACM Trans. Comput. Log."},{"issue":"4","key":"10.1016\/j.ejc.2026.104430_b25","article-title":"FO model checking of interval graphs","volume":"11","author":"Ganian","year":"2015","journal-title":"Log. Methods Comput. Sci."},{"issue":"1","key":"10.1016\/j.ejc.2026.104430_b26","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","article-title":"The intersection graphs of subtrees in trees are exactly the chordal graphs","volume":"16","author":"Gavril","year":"1974","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"10.1016\/j.ejc.2026.104430_b27","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0012-365X(78)90003-1","article-title":"A recognition algorithm for the intersection graphs of paths in trees","volume":"23","author":"Gavril","year":"1978","journal-title":"Discrete Math."},{"key":"10.1016\/j.ejc.2026.104430_b28","doi-asserted-by":"crossref","DOI":"10.1016\/j.ejc.2025.104247","article-title":"First order logic and twin-width in tournaments and dense oriented graphs","volume":"132","author":"Geniet","year":"2026","journal-title":"European J. Combin."},{"issue":"3","key":"10.1016\/j.ejc.2026.104430_b29","doi-asserted-by":"crossref","first-page":"17:1","DOI":"10.1145\/3051095","article-title":"Deciding first-order properties of nowhere dense graphs","volume":"64","author":"Grohe","year":"2017","journal-title":"J. ACM"},{"key":"10.1016\/j.ejc.2026.104430_b30","series-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014","first-page":"82","article-title":"Finding small patterns in permutations in linear time","author":"Guillemot","year":"2014"},{"issue":"1\u20132","key":"10.1016\/j.ejc.2026.104430_b31","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","article-title":"Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing","volume":"234","author":"Habib","year":"2000","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.ejc.2026.104430_b32","series-title":"Fundamentals of Domination in Graphs","author":"Haynes","year":"2013"},{"key":"10.1016\/j.ejc.2026.104430_b33","author":"Hlin\u011bn\u00fd","year":"2022","journal-title":"Pers. Commun."},{"key":"10.1016\/j.ejc.2026.104430_b34","first-page":"131","article-title":"Parameterized complexity of first-order logic","volume":"16","author":"Kreutzer","year":"2009","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"issue":"1","key":"10.1016\/j.ejc.2026.104430_b35","doi-asserted-by":"crossref","first-page":"10:1","DOI":"10.1145\/1435375.1435385","article-title":"Approximating rank-width and clique-width quickly","volume":"5","author":"Oum","year":"2008","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"10.1016\/j.ejc.2026.104430_b36","doi-asserted-by":"crossref","first-page":"101","DOI":"10.4064\/fm-100-2-101-107","article-title":"Stable graphs","volume":"100","author":"Podewski","year":"1978","journal-title":"Fund. Math."},{"key":"10.1016\/j.ejc.2026.104430_b37","doi-asserted-by":"crossref","unstructured":"M.Y. Vardi, The complexity of relational query languages, in: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, 1982, pp. 137\u2013146.","DOI":"10.1145\/800070.802186"}],"container-title":["European Journal of Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0195669826000983?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0195669826000983?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,9,19]],"date-time":"2026-09-19T16:18:19Z","timestamp":1789834699000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0195669826000983"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,12]]},"references-count":37,"alternative-id":["S0195669826000983"],"URL":"https:\/\/doi.org\/10.1016\/j.ejc.2026.104430","relation":{},"ISSN":["0195-6698"],"issn-type":[{"value":"0195-6698","type":"print"}],"subject":[],"published":{"date-parts":[[2026,12]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Twin-width VIIIa: Delineation","name":"articletitle","label":"Article Title"},{"value":"European Journal of Combinatorics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ejc.2026.104430","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier Ltd.","name":"copyright","label":"Copyright"}],"article-number":"104430"}}