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

2 Citations (Scopus)

Abstract

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
PublisherSpringer
Pages79-84
Number of pages6
Volume7579 LNCS
ISBN (Print)9783642341908
DOIs
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
https://link.springer.com/book/10.1007/978-3-642-34191-5

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

Conference

ConferenceSpanish Meeting on Computational Geometry 2011
Abbreviated titleEGC 2011
Country/TerritorySpain
CityAlcala de Henares
Period27/06/1130/06/11
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