{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:41:26Z","timestamp":1787323286511,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100031896","name":"University of Primorska","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100031896","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["948057"],"award-info":[{"award-number":["948057"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2019\/34\/E\/ST6\/00443"],"award-info":[{"award-number":["2019\/34\/E\/ST6\/00443"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2022\/46\/E\/ST6\/00143"],"award-info":[{"award-number":["2022\/46\/E\/ST6\/00143"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2019\/34\/E\/ST6\/00443"],"award-info":[{"award-number":["2019\/34\/E\/ST6\/00443"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2303251"],"award-info":[{"award-number":["DMS-2303251"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2202961"],"award-info":[{"award-number":["DMS-2202961"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"The Slovenian Research and Innovation Agency","doi-asserted-by":"publisher","award":["I0-0035"],"award-info":[{"award-number":["I0-0035"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"The Slovenian Research and Innovation Agency","doi-asserted-by":"publisher","award":["P1-0285"],"award-info":[{"award-number":["P1-0285"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"The Slovenian Research and Innovation Agency","doi-asserted-by":"publisher","award":["J1-3001"],"award-info":[{"award-number":["J1-3001"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"The Slovenian Research and Innovation Agency","doi-asserted-by":"publisher","award":["J1-3002"],"award-info":[{"award-number":["J1-3002"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"The Slovenian Research and Innovation Agency","doi-asserted-by":"publisher","award":["J1-3003"],"award-info":[{"award-number":["J1-3003"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"The Slovenian Research and Innovation Agency","doi-asserted-by":"publisher","award":["J1-4008"],"award-info":[{"award-number":["J1-4008"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"The Slovenian Research and Innovation Agency","doi-asserted-by":"publisher","award":["J1-4084"],"award-info":[{"award-number":["J1-4084"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004329","name":"The Slovenian Research and Innovation Agency","doi-asserted-by":"publisher","award":["N1-0370"],"award-info":[{"award-number":["N1-0370"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>For a tree decomposition [Formula: see text] of a graph [Formula: see text], let [Formula: see text] denote the maximum size of an induced matching in [Formula: see text] with the property that some bag of [Formula: see text] contains at least one endpoint of every edge of the matching. The induced matching treewidth of a graph [Formula: see text] is the minimum value of [Formula: see text] over all tree decompositions [Formula: see text] of [Formula: see text]. Classes of graphs with bounded induced matching treewidth admit polynomial-time algorithms for a number of problems, including Independent Set, [Formula: see text]-Coloring, Odd Cycle Transversal, and Feedback Vertex Set. In this paper, we focus on combinatorial properties of such classes. First, we show that graphs with bounded induced matching treewidth that exclude a fixed biclique as an induced subgraph have bounded tree-independence number, which is another well-studied parameter defined in terms of tree decompositions. This sufficient condition about excluding a biclique is also necessary, as bicliques have unbounded tree-independence number. Second, we show that graphs with bounded induced matching treewidth that exclude a fixed clique have bounded chromatic number, that is, classes of graphs with bounded induced matching treewidth are [Formula: see text]-bounded. The two results confirm two conjectures due to Lima et\u00a0al. [32 nd Annual European Symposium on Algorithms (ESA 2024), LIPIcs 308, pp. 85:1\u201385:17].<\/jats:p>","DOI":"10.1137\/24m1659960","type":"journal-article","created":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T04:00:32Z","timestamp":1747368032000},"page":"1189-1200","source":"Crossref","is-referenced-by-count":3,"title":["Excluding a Clique or a Biclique in Graphs of Bounded Induced Matching Treewidth"],"prefix":"10.1137","volume":"39","author":[{"given":"Tara","family":"Abrishami","sequence":"first","affiliation":[{"name":"University of Hamburg, Hamburg, 20146 Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1695-0188","authenticated-orcid":true,"given":"Marcin","family":"Bria\u0144ski","sequence":"additional","affiliation":[{"name":"Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Krak\u00f3w, 30-348 Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-0764-9613","authenticated-orcid":true,"given":"Jadwiga","family":"Czy\u017cewska","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warszawa, 02-097 Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rose","family":"McCarty","sequence":"additional","affiliation":[{"name":"School of Mathematics and School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Milani\u010d","sequence":"additional","affiliation":[{"name":"FAMNIT and IAM, University of Primorska, Koper, 6000 Slovenia."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":true,"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[{"name":"Faculty of Mathematics and Information Science, Warsaw University of Technology, Warsaw, 00-662 Poland, and University of Warsaw, Warszawa, 02-097 Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bartosz","family":"Walczak","sequence":"additional","affiliation":[{"name":"Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Krak\u00f3w, 30-348 Poland."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,5,16]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.23104"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-43380-1_6"},{"key":"ref4","volume-title":"Nonserial Dynamic Programming","author":"Bertel\u00e8 U.","year":"1972"},{"key":"ref5","unstructured":"N. Brettell, A. Munaro, D. Paulusma, and S. Yang, Comparing Width Parameters on Graph Classes, CoRR, abs\/2308.05817, 2023, https:\/\/doi.org\/10.48550\/arXiv.2308.05817."},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-023-00054-3"},{"key":"ref7","unstructured":"M. Chudnovsky, S. Hajebi, D. Lokshtanov, and S. Spirkl, Tree Independence Number II. Three-path-configurations, preprint, arXiv:2405.00265, 2024 https:\/\/doi.org\/10.48550\/arXiv.2405.00265."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.027"},{"key":"ref10","unstructured":"C. Dallard, F. V. Fomin, P. A. Golovach, T. Korhonen, and M. Milani\u010d, Computing tree decompositions with small independence number, in 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), LIPIcs 297, K. Bringmann, M. Grohe, G. Puppis, and O. Svensson, eds. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, 2024, pp. 51:1\u201351:18, https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2024.51."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.10.006"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2024.03.005"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(85)90044-5"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.09.006"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0017-8"},{"key":"ref17","unstructured":"P. T. Lima, M. Milani\u010d, P. Mur\u0161i\u010d, K. Okrasa, P. Rza\u017cewski, and K. \u0160torgel, Tree Decompositions Meet Induced Matchings: Beyond Max Weight Independent Set, preprint, arXiv:2402.15834, 2024, https:\/\/doi.org\/10.48550\/arXiv.2402.15834."},{"key":"ref18","unstructured":"P. T. Lima, M. Milani\u010d, P. Mur\u0161i\u010d, K. Okrasa, P. Rz\u0105\u017cewski, and K. \u0160torgel, Tree decompositions meet induced matchings: Beyond max weight independent set, in 32nd Annual European Symposium on Algorithms (ESA 2024), LIPIcs 308, T. Chan, J. Fischer, J. Iacono, and G. Herman, eds. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, 2024, pp. 85:1\u201385:17, https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2024.85."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1919"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00067-4"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22601"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"N. Yolov, Minor-matching hypertree width, in Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), New Orleans, LA, 2018, A. Czumaj, ed. SIAM, 2018, pp. 219\u2013233, https:\/\/doi.org\/10.1137\/1.9781611975031.16.","DOI":"10.1137\/1.9781611975031.16"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1659960","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:52:54Z","timestamp":1787320374000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1659960"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,16]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1137\/24M1659960"],"URL":"https:\/\/doi.org\/10.1137\/24m1659960","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,16]]}}}