Coloring KkKk-free intersection graphs of geometric objects in the plane

The intersection graph   of a collection CC of sets is the graph on the vertex set CC, in which C1,C2∈CC1,C2∈C are joined by an edge if and only if C1∩C2≠0̸C1∩C2≠0̸. Erdős conjectured that the chromatic number of triangle-free intersection graphs of nn segments in the plane is bounded from above by a constant. Here we show that it is bounded by a polylogarithmic function of nn, which is the first nontrivial bound for this problem. More generally, we prove that for any tt and kk, the chromatic number of every KkKk-free intersection graph of nn curves in the plane, every pair of which have at most tt points in common, is at most (ctlognlogk)clogk, where cc is an absolute constant and ctct only depends on tt. We establish analogous results for intersection graphs of convex sets, xx-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 large kk we improve the best known upper bound on the number of edges of a kk-quasi-planar topological graph   with nn vertices, that is, a graph drawn in the plane with curvilinear edges, no kk of which are pairwise crossing. As another application, we show that for every ε>0ε>0 and for every positive integer tt, there exist δ>0δ>0 and a positive integer n0n0 such that every topological graph with n≥n0n≥n0 vertices, at least n1+εn1+ε edges, and no pair of edges intersecting in more than tt points, has at least nδnδ pairwise intersecting edges.