2013/02/28 by Jacob Fox, János Pach, Fox, Jacob +1 · 3 citations
Computer Science · Mathematics · #05C10 #05C35 #05C55 #05C62 #05D10 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1302.7228
openalex publication_date 2013/02/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(√(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 Kt 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 Kt,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.