pith. sign in

arxiv: 1804.01057 · v1 · pith:UNRKIZ3Qnew · submitted 2018-04-03 · 🧮 math.CO · cs.CG

The exact chromatic number of the convex segment disjointness graph

classification 🧮 math.CO cs.CG
keywords graphchromaticconvexexactnumbersegmentstfracadjacent
0
0 comments X
read the original 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\'c and Wood [2007]. Improving on their estimates, we prove the following exact formula: $$\chi(D_n) = n - \left\lfloor \sqrt{2n + \tfrac{1}{4}} - \tfrac{1}{2}\right\rfloor.$$

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.