{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T21:33:44Z","timestamp":1750109624940,"version":"3.37.3"},"reference-count":18,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2023,11,21]],"date-time":"2023-11-21T00:00:00Z","timestamp":1700524800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/http\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550\u201022\u20101\u20100083"],"award-info":[{"award-number":["FA9550\u201022\u20101\u20100083"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>What are the unavoidable induced subgraphs of graphs with large treewidth? It is well\u2010known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the \u201cbasic treewidth obstructions\u201d). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so\u2010called \u201clayered wheels,\u201d contain wheels, where a <jats:italic>wheel<\/jats:italic> consists of a <jats:italic>hole<\/jats:italic> (i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth.<\/jats:p>","DOI":"10.1002\/jgt.23055","type":"journal-article","created":{"date-parts":[[2023,11,21]],"date-time":"2023-11-21T23:16:07Z","timestamp":1700608567000},"page":"542-561","update-policy":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Induced subgraphs and tree decompositions V. one neighbor in a hole"],"prefix":"10.1002","volume":"105","author":[{"given":"Tara","family":"Abrishami","sequence":"first","affiliation":[{"name":"Mathematics Department and PACM Princeton University Princeton New Jersey USA"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-5515-9145","authenticated-orcid":false,"given":"Bogdan","family":"Alecu","sequence":"additional","affiliation":[{"name":"School of Computing University of Leeds Leeds UK"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-8920-4944","authenticated-orcid":false,"given":"Maria","family":"Chudnovsky","sequence":"additional","affiliation":[{"name":"Mathematics Department and PACM Princeton University Princeton New Jersey USA"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-4551-7834","authenticated-orcid":false,"given":"Sepehr","family":"Hajebi","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada"}]},{"given":"Sophie","family":"Spirkl","sequence":"additional","affiliation":[{"name":"Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0003-3286-3145","authenticated-orcid":false,"given":"Kristina","family":"Vu\u0161kovi\u0107","sequence":"additional","affiliation":[{"name":"School of Computing University of Leeds Leeds UK"}]}],"member":"311","published-online":{"date-parts":[[2023,11,21]]},"reference":[{"key":"e_1_2_11_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2021.103394"},{"key":"e_1_2_11_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/11084933X"},{"key":"e_1_2_11_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.10.005"},{"key":"e_1_2_11_5_1","unstructured":"T.Abrishami M.Chudnovsky C.Dibek andK.Vu\u0161kovi\u0107 Submodular functions and perfect graphs.arXiv:2110.00108(2021)."},{"issue":"6","key":"e_1_2_11_6_1","first-page":"29","article-title":"Induced subgraphs and tree decompositions III. three\u2010path\u2010configurations and logarithmic treewidth","volume":"2022","author":"Abrishami T.","year":"2021","journal-title":"Adv. Comb"},{"key":"e_1_2_11_7_1","doi-asserted-by":"crossref","unstructured":"T.Abrishami M.Chudnovsky S.Hajebi andS.Spirkl.Induced subgraphs and tree decompositions IV. (Even hole diamond pyramid)\u2010free graphs Electron. J. Comb.30(2023) no.2.","DOI":"10.37236\/11623"},{"key":"e_1_2_11_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2022.05.009"},{"key":"e_1_2_11_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.017"},{"key":"e_1_2_11_10_1","doi-asserted-by":"crossref","unstructured":"H. L.Bodlaender Dynamic programming on graphs with bounded treewidth. Springer Berlin Heidelberg 1988 pp.105\u2013118.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"e_1_2_11_11_1","doi-asserted-by":"crossref","unstructured":"M.Cygan F. V.Fomin L.Kowalik D.Lokshtanov D.Marx M.Pilipczuk M.Pilipczuk andS.Saurabh Parameterized algorithms. Springer 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_2_11_12_1","doi-asserted-by":"crossref","unstructured":"J.Davies An Oberwolfach technical report.https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.4171\/OWR\/2022\/1","DOI":"10.4171\/OWR\/2022\/1"},{"key":"e_1_2_11_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22030"},{"key":"e_1_2_11_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2023.01.002"},{"key":"e_1_2_11_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_11_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"e_1_2_11_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_2_11_18_1","unstructured":"C.Pohoata Unavoidable induced subgraphs of large graphs Senior Thesis Princeton University 2014."},{"key":"e_1_2_11_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22666"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.23055","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.23055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T15:20:09Z","timestamp":1707751209000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.23055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,21]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10.1002\/jgt.23055"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1002\/jgt.23055","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"type":"print","value":"0364-9024"},{"type":"electronic","value":"1097-0118"}],"subject":[],"published":{"date-parts":[[2023,11,21]]},"assertion":[{"value":"2022-06-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}