Applications of a New Separator Theorem for String Graphs
An intersection graph of curves in the plane is called a string graph. Matousek almost completely settled a conjecture of the authors by showing that every string graph with m edges admits a vertex separator of size O(√m log m). In the present note, this bound is combined with a result of the author...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Cambridge University Press
2015
|
| Online Access: | http://hdl.handle.net/1721.1/92846 |
| _version_ | 1824457850267631616 |
|---|---|
| author | Fox, Jacob Pach, Janos |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob Pach, Janos |
| author_sort | Fox, Jacob |
| collection | MIT |
| description | An intersection graph of curves in the plane is called a string graph. Matousek almost completely settled a conjecture of the authors by showing that every string graph with m edges admits a vertex separator of size O(√m log m). 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 G with n vertices: (i) if K[subscript t] ⊈ G for some t, then the chromatic number of G is at most (log n) [superscript O(log t)]; (ii) if K[subscript t,t] ⊈ G, then G has at most t(log t) [superscript O(1)] n edges; and (iii) a lopsided Ramsey-type result, which shows that the Erdos–Hajnal conjecture almost holds for string graphs. |
| first_indexed | 2024-09-23T14:27:34Z |
| format | Article |
| id | mit-1721.1/92846 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:27:34Z |
| publishDate | 2015 |
| publisher | Cambridge University Press |
| record_format | dspace |
| spelling | mit-1721.1/928462022-10-01T21:24:59Z Applications of a New Separator Theorem for String Graphs Fox, Jacob Pach, Janos Massachusetts Institute of Technology. Department of Mathematics Fox, Jacob An intersection graph of curves in the plane is called a string graph. Matousek almost completely settled a conjecture of the authors by showing that every string graph with m edges admits a vertex separator of size O(√m log m). 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 G with n vertices: (i) if K[subscript t] ⊈ G for some t, then the chromatic number of G is at most (log n) [superscript O(log t)]; (ii) if K[subscript t,t] ⊈ G, then G has at most t(log t) [superscript O(1)] n edges; and (iii) a lopsided Ramsey-type result, which shows that the Erdos–Hajnal conjecture almost holds for string graphs. Simons Foundation (Fellowship) National Science Foundation (U.S.) (Grant DMS-1069197) Alfred P. Sloan Foundation (Fellowship) NEC Corporation (MIT Award) 2015-01-14T13:50:00Z 2015-01-14T13:50:00Z 2013-10 2013-08 Article http://purl.org/eprint/type/JournalArticle 0963-5483 1469-2163 http://hdl.handle.net/1721.1/92846 Fox, Jacob, and Janos Pach. “Applications of a New Separator Theorem for String Graphs.” Combinatorics, Probability and Computing 23, no. 01 (January 2014): 66–74. en_US http://dx.doi.org/10.1017/S0963548313000412 Combinatorics, Probability and Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Cambridge University Press MIT web domain |
| spellingShingle | Fox, Jacob Pach, Janos Applications of a New Separator Theorem for String Graphs |
| title | Applications of a New Separator Theorem for String Graphs |
| title_full | Applications of a New Separator Theorem for String Graphs |
| title_fullStr | Applications of a New Separator Theorem for String Graphs |
| title_full_unstemmed | Applications of a New Separator Theorem for String Graphs |
| title_short | Applications of a New Separator Theorem for String Graphs |
| title_sort | applications of a new separator theorem for string graphs |
| url | http://hdl.handle.net/1721.1/92846 |
| work_keys_str_mv | AT foxjacob applicationsofanewseparatortheoremforstringgraphs AT pachjanos applicationsofanewseparatortheoremforstringgraphs |