Coloring k k -free intersection graphs of geometric objects in the plane
Jacob Fox, János Pach · 2008
The intersection graph of a collection C of sets is a graph on the vertex set C, in which C1,C2 ∈ C are joined by an edge if and only if C1 ∩ C2 ≠ Ø. Erdös 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 Kk-free intersection graph of n curves in the plane, every pair of which have at most t points in common, is at most (ct log n/log k)c log k, where c is an absolute constant and ct 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.