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(root 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 not subset of G for some t, then the chromatic number of G is at most (log n)(O(log t)); (ii) if K-t,K-t not subset 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.


Published in:
Combinatorics, Probability and Computing, 23, 01, 66-74
Year:
2014
Publisher:
New York, Cambridge Univ Press
ISSN:
1469-2163
Laboratories:




 Record created 2014-07-28, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)