The chromatic number of the convex segment disjointness graph

Ruy Fabila-Monroy; David R. Wood

paper

The chromatic number of the convex segment disjointness graph

arXiv:1105.4931

Abstract

Let $P$ be a set of $n$ points in general and 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 et al. [\emph{CGTA}, 2005]. The previous best bounds are $\frac{3 n}{4} \leq χ (D_{n}) < n - \frac{n}{2}$ (ignoring lower order terms). In this paper we improve the lower bound to $χ (D_{n}) \geq n - 2 n$ , to conclude a near-tight bound on $χ (D_{n})$ .

arXiv commentXIV Spanish Meeting on Computational Geometry Alcalá de Henares, Spain, June 27--30, 2011