{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,19]],"date-time":"2026-09-19T01:55:16Z","timestamp":1789782916631,"version":"4.0.1"},"reference-count":42,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["647678"],"award-info":[{"award-number":["647678"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001779","name":"Monash University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001779","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>A graph $G$ is Ramsey for a graph $H$ if every 2-coloring of the edges of $G$ contains a monochromatic copy of $H$. We consider the following question: if $H$ has bounded treewidth, is there a \u201csparse\u201d graph $G$ that is Ramsey for $H$? Two notions of sparsity are considered. Firstly, we show that if the maximum degree and treewidth of $H$ are bounded, then there is a graph $G$ with $O(|V(H)|)$ edges that is Ramsey for $H$. This was previously only known for the smaller class of graphs $H$ with bounded bandwidth. On the other hand, we prove that in general the treewidth of a graph $G$ that is Ramsey for $H$ cannot be bounded in terms of the treewidth of $H$ alone. In fact, the latter statement is true even if the treewidth is replaced by the degeneracy and $H$ is a tree.<\/jats:p>","DOI":"10.1137\/20m1335790","type":"journal-article","created":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T10:21:32Z","timestamp":1614680492000},"page":"281-293","source":"Crossref","is-referenced-by-count":15,"title":["The Size Ramsey Number of Graphs with Bounded Treewidth"],"prefix":"10.1137","volume":"35","author":[{"given":"Nina","family":"Kamcev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2840-0546","authenticated-orcid":true,"given":"Anita","family":"Liebenau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8866-3041","authenticated-orcid":true,"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liana","family":"Yepremyan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,3,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-013-2778-4"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070115"},{"key":"atypb4","first-page":"34","author":"Beck J.","year":"1990","journal-title":"New York"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s,\n                      Random Graphs\n                      , 2nd ed., Cambridge Stud. Adv. Math. 73, Cambridge University Press, Cambridge, 2001,https:\/\/doi.org\/10.1017\/CBO9780511814068.","DOI":"10.1017\/CBO9780511814068"},{"key":"atypb8","first-page":"167","volume":"1","author":"Burr S. A.","year":"1976","journal-title":"Ars Combin."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22432"},{"key":"atypb10","unstructured":"D. Clemens, M. Miralaie, D. Reding, M. Schacht, and A. Taraz,\n                      On the Size-Ramsey Number of Grid Graphs\n                      , preprint, arXiv:1906.06915 [math.co], 2019."},{"key":"atypb11","unstructured":"D. Conlon,\n                      Question Suggested for the ATI-HIMR Focused Research Workshop: Large-Scale Structures in Random Graphs\n                      , Alan Turing Institute, December 2016."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548313000448"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20363"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200412"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050001"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1017\/S096354831400056X"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579245"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579174"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018930"},{"key":"atypb20","first-page":"609","author":"Erd\u00f6s P.","year":"1975","journal-title":"Amstardam"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/0118004"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2014.06.003"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20199"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"J. Friedman,\n                      A Proof of Alon's Second Eigenvalue Conjecture and Related Problems\n                      , Mem. Amer. Math. Soc., 910, American Mathematical Society, Providence, RI, 2008.","DOI":"10.1090\/memo\/0910"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579202"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2020.06.004"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22030"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02808204"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548300001619"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.37236\/2526"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.08.004"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040106"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.4064\/cm-3-1-50-57"},{"key":"atypb34","first-page":"199","author":"Krivelevich M.","year":"2006","journal-title":"New York"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2013.07.023"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90015-0"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2016.06.009"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/18M1199125"},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"B. A. Reed,\n                      Algorithmic aspects of tree width\n                      , in Recent Advances in Algorithms and Combinatorics, CMS Books Math.\/Ouvrages Math. SMC 11, Springer, New York, 2003, pp. 85-107,https:\/\/doi.org\/10.1007\/0-387-22444-0_4.","DOI":"10.1007\/0-387-22444-0_4"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070024"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20445"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2008.11.010"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00047-8"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1335790","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:19:14Z","timestamp":1787321954000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1335790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1335790"],"URL":"https:\/\/doi.org\/10.1137\/20m1335790","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}