The exact chromatic number of the convex segment disjointness graph

04/03/2018
by   Ruy Fabila-Monroy, et al.
0

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: χ(D_n) = n - √(2n + 14) - 12.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset