The Chromatic Number of the Convex Segment Disjointness Graph

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 \(\frac{3n}{4}\leq \chi(D_n)

Keywords:

• Chromatic scale
• Vertex (geometry)
• Discrete mathematics
• Combinatorics
• Computational geometry
• Line segment
• Regular polygon
• Mathematics
• Disjoint sets
• Topology
• Convex position
• Upper and lower bounds
• Constructive

• Correction
• Source
• Cite
• Save
• Machine Reading By IdeaReader