### November 24, 2017, 14:15pm

### Tóth Géza: Disjointness graphs of segments in the space

The {\em disjointness graph} $G=G({\cal S})$
of a set of segments ${\cal S}$ in
${R}^d$, $d\ge 2,$ is a graph whose vertex set is
${\cal S}$ and two vertices are connected by
an edge if and only if the corresponding segments are disjoint. We prove that
the chromatic number of $G$ satisfies $\chi(G)\le(\omega(G))^4+(\omega(G))^3$,
where $\omega(G)$ denotes the clique number of $G$. It follows that $\cal S$ has
$\Omega(n^{1/5})$ pairwise intersecting or pairwise disjoint
elements. Stronger bounds are established for lines in space, instead of
segments.
We show that computing $\omega(G)$ and $\chi(G)$ for disjointness graphs of
lines in space are NP-hard tasks. However, we can design efficient
algorithms to compute proper colorings of $G$ in which the number of colors
satisfies the above upper bounds. One cannot expect similar results for sets
of continuous arcs, instead of segments, even in the plane. We construct
families of arcs whose disjointness graphs are triangle-free ($\omega(G)=2$),
but whose chromatic numbers are arbitrarily large.

Joint work with János Pach and Gábor Tardos.