The Maximum Chromatic Number of the Disjointness Graph of Segments on $n$-point Sets in the Plane with $n\le 16$

Abstract

Let $P$ be a finite set of points in general position in the plane. The disjointness graph of segments $D(P)$ of $P$ is the graph whose vertices are all the closed straight line segments with endpoints in $P$, two of which are adjacent in $D(P)$ if and only if they are disjoint. As usual, we use $\chi (D(P))$ to denote the chromatic number of $D(P)$, and use $d(n)$ to denote the maximum $\chi (D(P))$ taken over all sets $P$ of $n$ points in general position in the plane. In this paper we show that $d(n)=n-2$ if and only if $n\in \{3,4,\dots ,16\}$.

25 pages, 3 figures