The chromatic number of the convex segment disjointness graph

2011/05/25 by Fabila-Monroy, Ruy, Wood, David R. · 1 citation
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/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. [CGTA, 2005]. The previous best bounds are (3n)/(4)≤χ(D_n)

Cited by

• On Grundy indices for complete geometric graphs

Related

• The exact chromatic number of the convex segment disjointness graph
• The Maximum Chromatic Number of the Disjointness Graph of Segments on n-point Sets in the Plane with n≤ 16
• Disjointness graphs of segments
• ?, ?, and ?
• On the chromatic number of disjointness graphs of curves