Applications of a New Separator Theorem for String Graphs
Open Access
- 25 October 2013
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 23 (1) , 66-74
Abstract
An intersection graph of curves in the plane is called astring graph. Matoušek almost completely settled a conjecture of the authors by showing that every string graph withmedges admits a vertex separator of size $O(\sqrt{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 graphsGwithnvertices: (i) ifKt⊈Gfor somet, then the chromatic number ofGis at most (logn)O(logt); (ii) ifKt,t⊈G, thenGhas at mostt(logt)O(1)nedges,; and (iii) a lopsided Ramsey-type result, which shows that the Erdős–Hajnal conjecture almost holds for string graphs.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- String graphs and incomparability graphsAdvances in Mathematics, 2012
- Eigenvalue bounds, spectral partitioning, and metrical deformations via flowsJournal of the ACM, 2010
- A bipartite strengthening of the Crossing LemmaJournal of Combinatorial Theory, Series B, 2010
- On the Maximum Number of Edges in Topological Graphs with no Four Pairwise Crossing EdgesDiscrete & Computational Geometry, 2009
- Separator theorems and Turán-type results for planar intersection graphsAdvances in Mathematics, 2008
- On planar intersection graphs with forbidden subgraphsJournal of Graph Theory, 2008
- Improved Approximation Algorithms for Minimum Weight Vertex SeparatorsSIAM Journal on Computing, 2008
- The discharging method in combinatorial geometry and the Pach-Sharir conjecture2008
- Quasi-planar graphs have a linear number of edgesCombinatorica, 1997
- New lower bound techniques for VLSITheory of Computing Systems, 1984