Coloring Kk-free Intersection Graphs of Geometric Objects in the Plane

The intersection graph of a collection C of sets is a graph on the vertex set C, in which C-1, C-2 is an element of C are joined by an edge if and only if C-1 boolean AND C-2 not equal 0. Erdos conjectured that the chromatic number of triangle-free intersection graphs of n segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of n, which is the first nontrivial bound for this problem. More generally, we prove that for any t and k, the chromatic number of every K-k-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (C-t log n/log k)(c log k), where c is an absolute constant and c(t) only depends on t. We establish analogous results for intersection graphs of convex sets, x-monotone curves, semialgebraic sets of constant description complexity, and sets that can be obtained as the union of a bounded number of sets homeomorphic to a disk. Using a mix of results on partially ordered sets and planar separators, for laxge k we improve the best known upper bound on the number of edges of a k-quasi-planar topological graph with n vertices, that is, a graph drawn in the plane with curvilinear edges, no k of which are pairwise crossing. As another application, we show that for every epsilon > 0 and for every positive integer t, there exist delta > 0 and a positive integer n(0) such that every topological graph with n >= n(0) vertices, at least n(1+epsilon) edges, and no pair of edges intersecting in more than t points, has at least n(delta) pairwise intersecting edges.