2023/01/18 by Fabila-Monroy, Ruy · 1 citation
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2301.07261
A geometric graph is a graph whose vertex set is a set of points in general position in the plane, and its edges are straight line segments joining these points. We show that for every integer k ≥ 2, there exists a constat c>0 such that the following holds. The edges of every dense geometric graph can be colored with k colors, such that the number of pairs of edges of the same color that cross is at most (1/k-c) times the total number of pairs of edges that cross. The case when k=2 and G is a complete geometric graph, was proved by Aichholzer et al.[GD 2019].