{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T22:39:16Z","timestamp":1769121556612,"version":"3.49.0"},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2013,10,25]],"date-time":"2013-10-25T00:00:00Z","timestamp":1382659200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>An intersection graph of curves in the plane is called a<jats:italic>string graph<\/jats:italic>. Matou\u0161ek almost completely settled a conjecture of the authors by showing that every string graph with<jats:italic>m<\/jats:italic>edges admits a vertex separator of size<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548313000412_inline1\"\/><jats:tex-math>$O(\\sqrt{m}\\log m)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. In the present note, this bound is combined with a result of the authors, according to which every dense string graph contains a large complete balanced bipartite graph. Three applications are given concerning string graphs<jats:italic>G<\/jats:italic>with<jats:italic>n<\/jats:italic>vertices: (i) if<jats:italic>K<jats:sub>t<\/jats:sub><\/jats:italic>\u2288<jats:italic>G<\/jats:italic>for some<jats:italic>t<\/jats:italic>, then the chromatic number of<jats:italic>G<\/jats:italic>is at most (log<jats:italic>n<\/jats:italic>)<jats:sup><jats:italic>O<\/jats:italic>(log<jats:italic>t<\/jats:italic>)<\/jats:sup>; (ii) if<jats:italic>K<jats:sub>t,t<\/jats:sub><\/jats:italic>\u2288<jats:italic>G<\/jats:italic>, then<jats:italic>G<\/jats:italic>has at most<jats:italic>t<\/jats:italic>(log<jats:italic>t<\/jats:italic>)<jats:sup><jats:italic>O<\/jats:italic>(1)<\/jats:sup><jats:italic>n<\/jats:italic>edges,; and (iii) a lopsided Ramsey-type result, which shows that the Erd\u0151s\u2013Hajnal conjecture almost holds for string graphs.<\/jats:p>","DOI":"10.1017\/s0963548313000412","type":"journal-article","created":{"date-parts":[[2013,10,25]],"date-time":"2013-10-25T13:26:34Z","timestamp":1382707594000},"page":"66-74","source":"Crossref","is-referenced-by-count":41,"title":["Applications of a New Separator Theorem for String Graphs"],"prefix":"10.1017","volume":"23","author":[{"given":"JACOB","family":"FOX","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00c1NOS","family":"PACH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,10,25]]},"reference":[{"key":"S0963548313000412_ref17","article-title":"Near-optimal separators in string graphs","author":"Matou\u0161ek","year":"2013","journal-title":"Comb. Probab. Comput."},{"key":"S0963548313000412_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744433"},{"key":"S0963548313000412_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2012.03.011"},{"key":"S0963548313000412_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990459"},{"key":"S0963548313000412_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-009-9143-9"},{"key":"S0963548313000412_ref15","doi-asserted-by":"crossref","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","article-title":"On a problem of K. Zarankiewicz.","volume":"3","author":"K\u0151v\u00e1ri","year":"1954","journal-title":"Colloq. Math."},{"key":"S0963548313000412_ref21","unstructured":"Pawlik A. , Kozik J. , Krawczyk T. , Laso\u0144 M. , Micek P. , Trotter W. T. and Walczak B. (2012) Triangle-free intersection graphs of line segments with large chromatic number. Preprint. arXiv:1209.1595"},{"key":"S0963548313000412_ref22","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/453\/08806"},{"key":"S0963548313000412_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90045-0"},{"key":"S0963548313000412_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20332"},{"key":"S0963548313000412_ref5","doi-asserted-by":"crossref","unstructured":"Chudnovsky M. (2013) The Erd\u0151s\u2013Hajnal conjecture: A survey. J. Graph Theory, to appear.","DOI":"10.1002\/jgt.21730"},{"key":"S0963548313000412_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.06.002"},{"key":"S0963548313000412_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2009.03.005"},{"key":"S0963548313000412_ref18","first-page":"273","volume-title":"Discrete and Computational Geometry","author":"Pach","year":"1991"},{"key":"S0963548313000412_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-44400-8_24"},{"key":"S0963548313000412_ref3","first-page":"9","volume-title":"Theory and Practice of Combinatorics","author":"Ajtai","year":"1982"},{"key":"S0963548313000412_ref7","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"S0963548313000412_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.021"},{"key":"S0963548313000412_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01196127"},{"key":"S0963548313000412_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706593"},{"key":"S0963548313000412_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s11083-006-9043-z"},{"key":"S0963548313000412_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77200-2_4"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000412","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T09:17:58Z","timestamp":1564564678000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000412\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,25]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["S0963548313000412"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000412","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,25]]}}}