The chromatic number of the convex segment disjointness graph

Ruy Fabila-Monroy, David R. Wood

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

4 Citations (Scopus)


Let P be a set of n points in general and convex position in the plane. Let Dn 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. [CGTA, 2005]. The previous best bounds are 3n/4 ≤ χ(Dn) < n - √n/2 (ignoring lower order terms). In this paper we improve the lower bound to χ(Dn) ≥ n - √2n, achieving near-tight bounds on χ(Dn).

Original languageEnglish
Title of host publicationComputational Geometry
Subtitle of host publicationXIV Spanish Meeting, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Revised Selected Papers
Number of pages6
Volume7579 LNCS
ISBN (Print)9783642341908
Publication statusPublished - 2012
Externally publishedYes
EventSpanish Meeting on Computational Geometry 2011 - University of Alcala, Alcala de Henares, Spain
Duration: 27 Jun 201130 Jun 2011
Conference number: 14th

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7579 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


ConferenceSpanish Meeting on Computational Geometry 2011
Abbreviated titleEGC 2011
CityAlcala de Henares
OtherComputational Geometry
XIV Spanish Meeting on Computational Geometry, EGC 2011, Dedicated to Ferran Hurtado on the Occasion of His 60th Birthday, Alcalá de Henares, Spain, June 27-30, 2011, Revised Selected Papers
Internet address

Cite this