Résume | Let $\omega(G)$ and $\chi(G)$ denote the clique number and chromatic number of a graph $G$, respectively. The disjointness graph of a family of curves (continuous arcs in the plane) is the graph whose vertices correspond to the curves and in which two vertices are joined by an edge if and only if the corresponding curves are disjoint. A curve is called $x$-monotone if every vertical line intersects it in at most one point.
We solve a 25 years old problem by showing that for arbitrarily large integers $k$, there exist families of $x$-monotone curves such that their disjointness graphs $G$ satisfy $\omega(G)=k$ and $\chi(G)=\Omega(k^4)$. This bound is asymptotically tight.
If we drop the condition that the curves are $x$-monotone, then $\chi(G)$ cannot be bounded in terms of $k$. We construct, for every $g>3$, families of $n$ curves such that the girth of their disjointness graphs $G$ is at least $g$ and $\chi(G)=\Omega_g(\log n)$. This improves a result of Bollobás. Joint work with István Tomon. |