Applications of a new separator theorem for string graphs
From MaRDI portal
Abstract: 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 of m edges 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 graphs G with n vertices: (i) if K_t is not a subgraph of G for some t, then the chromatic number of G is at most (log n)^{O(log t)}; (ii) if K_{t,t} is not a subgraph of G, then G has at most t(log t)^{O(1)}n edges,; and (iii) a lopsided Ramsey-type result, which shows that the Erdos-Hajnal conjecture almost holds for string graphs.
Recommendations
Cites work
- A bipartite analogue of Dilworth's theorem
- A bipartite strengthening of the crossing Lemma
- A separator theorem for string graphs and its applications
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- New lower bound techniques for VLSI
- On the maximum number of edges in topological graphs with no four pairwise crossing edges
- Quasi-planar graphs have a linear number of edges
- Ramsey-type theorems
- Separator theorems and Turán-type results for planar intersection graphs
- String graphs and incomparability graphs
Cited in
(40)- Separators in region intersection graphs
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Characterization of 2-path signed network
- On the Zarankiewicz problem for intersection hypergraphs
- Coloring triangle-free L-graphs with \(O (\log \log n)\) colors
- Orthogonal tree decompositions of graphs
- Quasi-planar Graphs
- Two-Planar Graphs Are Quasiplanar
- Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
- Optimality program in segment and string graphs
- Graph product structure for non-minor-closed classes
- Decomposition of Multiple Packings with Subquadratic Union Complexity
- Zarankiewicz's problem for semi-algebraic hypergraphs
- On-line approach to off-line coloring problems on graphs with geometric representations
- Conflict-free coloring of string graphs
- The effect of planarization on width
- Ramsey properties of semilinear graphs
- Separator theorems and Turán-type results for planar intersection graphs
- Hasse diagrams with large chromatic number
- Clustered coloring of graphs with bounded layered treewidth and bounded degree
- A separator theorem for string graphs and its applications
- Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
- Coloring curves that cross a fixed curve
- Near-optimal separators in string graphs
- String graphs have the Erdős-Hajnal property
- Coloring triangle-free L-graphs with O( n) colors
- Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
- String graphs and separators
- Shortest path separators in unit disk graphs
- On the Size of Planarly Connected Crossing Graphs
- Coloring lines and Delaunay graphs with respect to boxes
- On string graph limits and the structure of a typical string graph
- 1-planar unit distance graphs
- A sharp threshold phenomenon in string graphs
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Quantitative restrictions on crossing patterns
- Notes on graph product structure theory
- A survey of degree-boundedness
- A Separator Theorem for String Graphs and Its Applications
- Outerstring graphs are -bounded
This page was built for publication: Applications of a new separator theorem for string graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5414146)
