Track: Optimization
Abstract
We study the minimum number of colors with which the intersection points of a set of line segments can be colored so that no segment contains points with the same color. We investigate the computational complexity of this problem, and give exact results and bounds for the chromatic numbers of different families of lines and line segments, including those corresponding to complete bipartite graphs, cactus graphs, and triangle-free graphs. We also relate the problem to the famous Erdos-Faber-Lovasz conjecture, and discuss computational experiments for certain randomly generated sets of segments.