The exact chromatic number of the convex segment disjointness graph

Abstract

Let $P$ be a set of $n$ points in strictly convex position in the plane. Let $D_n$ be the graph whose vertex set is the set of all line segments with endpoints in $P$, where disjoint segments are adjacent. The chromatic number of this graph was first studied by Araujo, Dumitrescu, Hurtado, Noy, and Urrutia [2005] and then by Dujmović and Wood [2007]. Improving on their estimates, we prove the following exact formula: $$\chi (D_n)=n-\lfloor \sqrt{2n+\frac{1}{4}}-\frac{1}{2}\rfloor .$$

Cited by in corpus (2)

• On the connectivity of the disjointness graph of segments of point sets in general position in the plane
• Thickness and Antithickness of Graphs