pith. sign in

arxiv: 1105.4931 · v2 · pith:AC6SLTUJnew · submitted 2011-05-25 · 🧮 math.CO · cs.CG

The chromatic number of the convex segment disjointness graph

classification 🧮 math.CO cs.CG
keywords graphboundchromaticconvexfraclowernumbersegments
0
0 comments X
read the original 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{3n}{4}\leq\chi(D_n) <n-\sqrt{\frac{n}{2}}$ (ignoring lower order terms). In this paper we improve the lower bound to $\chi(D_n)\geq n-\sqrt{2n}$, to conclude a near-tight bound on $\chi(D_n)$.

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.