{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:05:26Z","timestamp":1787321126517,"version":"build-2736575974"},"reference-count":93,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100004329","name":"Javna Agencija za Raziskovalno Dejavnost RS","doi-asserted-by":"publisher","award":["I0-0035"],"award-info":[{"award-number":["I0-0035"]}],"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":[[2021,1]]},"abstract":"<jats:p>Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition for a graph class to have bounded treewidth is the absence of large cliques. We study graph classes closed under taking induced subgraphs in which this condition is also sufficient, which we call $({tw},\\omega)$-bounded. Such graph classes are known to have useful algorithmic applications related to variants of the clique and $k$-coloring problems. We consider six well-known graph containment relations: the minor, topological minor, subgraph, induced minor, induced topological minor, and induced subgraph relations. For each of them, we give a complete characterization of the graphs $H$ for which the class of graphs excluding $H$ is $({tw},\\omega)$-bounded. Our results yield an infinite family of $\\chi$-bounded induced-minor-closed graph classes and imply that the class of 1-perfectly orientable graphs is $({tw},\\omega)$-bounded, leading to linear-time algorithms for $k$-coloring 1-perfectly orientable graphs for every fixed $k$. This answers a question of Bre\u0161ar, Hartinger, Kos, and Milani\u010d from 2018 and one of Beisegel, Chudnovsky, Gurvich, Milani\u010d, and Servatius from 2019, respectively. We also reveal some further algorithmic implications of $({tw},\\omega)$-boundedness related to list $k$-coloring and clique problems. In addition, we propose a question about the complexity of the maximum weight independent set problem in $({tw},\\omega)$-bounded graph classes and prove that the problem is polynomial-time solvable in every class of graphs excluding a fixed star as an induced minor.<\/jats:p>","DOI":"10.1137\/20m1352119","type":"journal-article","created":{"date-parts":[[2021,11,4]],"date-time":"2021-11-04T15:37:28Z","timestamp":1636040248000},"page":"2618-2646","source":"Crossref","is-referenced-by-count":11,"title":["Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure"],"prefix":"10.1137","volume":"35","author":[{"given":"Cl\u00e9ment","family":"Dallard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Milani\u010d","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kenny","family":"\u0160torgel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,11,4]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00158-3"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1069"},{"key":"atypb5","first-page":"126","author":"Beisegel J.","year":"2019","journal-title":"Cham"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.03.016"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0234-8"},{"key":"atypb8","first-page":"178","volume":"7","author":"Berman P.","year":"2000","journal-title":"Nordic J. Comput."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.05.005"},{"key":"atypb10","first-page":"574","author":"Bodlaender H.","year":"1998","journal-title":"New York"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender and A. M. C. A. Koster,\n                      Treewidth computations \\textupII. Lower bounds\n                      , Inform. and Comput., 209 (2011), pp. 1103-1119,https:\/\/doi.org\/10.1016\/j.ic.2011.04.003.","DOI":"10.1016\/j.ic.2011.04.003"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0399-9"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. Bonamy and M. Pilipczuk,\n                      Graphs of bounded cliquewidth are polynomially $\\chi$-bounded\n                      , Adv. Comb. (2020), 8,https:\/\/doi.org\/10.19086\/aic.13668.","DOI":"10.19086\/aic.13668"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.09.017"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.09.004"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22146"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.37236\/4424"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.endm.2017.06.042"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3467-x"},{"key":"atypb23","first-page":"256","author":"Chuzhoy J.","year":"2015","journal-title":"PA"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.09.010"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"atypb27","first-page":"1","author":"Dabrowski K. K.","year":"2019","journal-title":"UK"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.09.001"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"R. Diestel,\n                      Graph Theory\n                      , 5th ed., Grad. Texts in Math. 173, Springer, Berlin, 2017,https:\/\/doi.org\/10.1007\/978-3-662-53622-3.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190160509"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-27.1.85"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1965-052-0"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00097-3"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.12.005"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-003-9"},{"key":"atypb36","unstructured":"L. Esperet,\n                      Graph Colorings, Flows and Perfect Matchings\n                      , habilitation thesis, Universit\u00e9 Grenoble Alpes, 2017."},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190507"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.02.008"},{"key":"atypb40","first-page":"211","volume":"15","author":"Frank A.","year":"1976","journal-title":"Congr. Numer."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0495-5"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22028"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.08.008"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , 2nd ed., Ann. Discrete Math. 57, Elsevier Science B.V., Amsterdam, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"atypb45","first-page":"479","author":"Grohe M.","year":"2011","journal-title":"New York"},{"key":"atypb46","first-page":"413","volume":"19","author":"Gy\u00e1rf\u00e1s A.","year":"1987","journal-title":"Zastos. Mat."},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.37236\/595"},{"key":"atypb48","unstructured":"T. R. Hartinger,\n                      New Characterizations in Structural Graph Theory: \\textup1-Perfectly Orientable Graphs, Graph Products, and the Price of Connectivity\n                      , PhD thesis, University of Primorska, 2017."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22067"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.03.007"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2014.04.014"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00085-6"},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"T. R. Jensen and B. Toft,\n                      Graph Coloring Problems\n                      , Wiley Ser. Discrete Math. Optim., John Wiley & Sons, New York, 1995.","DOI":"10.1002\/9781118032497"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1007\/BF01359971"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.08.022"},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2017.02.018"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-034-0"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"atypb60","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.09.003"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.02.015"},{"key":"atypb62","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1058"},{"key":"atypb63","first-page":"75","volume":"43","author":"Lov\u00e1sz L.","year":"2006","journal-title":"S.)"},{"key":"atypb64","doi-asserted-by":"crossref","unstructured":"V. Lozin and I. Razgon,\n                      Tree-Width Dichotomy\n                      , preprint,arXiv:2012.01115[math.CO], 2021.","DOI":"10.1016\/j.ejc.2022.103517"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-015-9872-z"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1996.0030"},{"key":"atypb67","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(80)90074-X"},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.44.194"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.11.001"},{"key":"atypb70","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00048-8"},{"key":"atypb71","first-page":"264","volume":"30","author":"Ramsey F. P.","year":"1929","journal-title":"Proc. Lond. Math. Soc. (2)"},{"key":"atypb72","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-003-0540-1"},{"key":"atypb73","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"atypb74","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"atypb76","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.002"},{"key":"atypb77","unstructured":"P. Scheffler,\n                      What graphs have bounded tree-width?\n                      , in Proceedings of the 7th Fischland Colloquium, III (Wustrow, 1988), 1990, pp. 31-38."},{"key":"atypb78","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-017-9775-8"},{"key":"atypb79","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22601"},{"key":"atypb80","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.0.CO;2-J"},{"key":"atypb81","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.07.010"},{"key":"atypb82","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1966.tb01713.x"},{"key":"atypb83","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22666"},{"key":"atypb84","first-page":"155","author":"Skodinis K.","year":"1999","journal-title":"Berlin"},{"key":"atypb85","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(77)90044-9"},{"key":"atypb86","first-page":"557","author":"Sumner D. P.","year":"1981","journal-title":"New York"},{"key":"atypb87","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22214"},{"key":"atypb88","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.05.005"},{"key":"atypb89","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2019.04.004"},{"key":"atypb90","unstructured":"D. B. West,\n                      Introduction to Graph Theory\n                      , Prentice Hall, Upper Saddle River, NJ, 1996."},{"key":"atypb91","doi-asserted-by":"publisher","DOI":"10.1613\/jair.4030"},{"key":"atypb92","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.03.025"},{"key":"atypb93","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1352119","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:36Z","timestamp":1787317596000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1352119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":93,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1352119"],"URL":"https:\/\/doi.org\/10.1137\/20m1352119","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}