2012/07/18 by Balázs Keszegh, Nathan Lemons, Keszegh, Balázs +3 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1207.4415
We consider proper online colorings of hypergraphs defined by geometric regions. We prove that there is an online coloring algorithm that colors N intervals of the real line using Θ(log N/k) colors such that for every point p, contained in at least k intervals, not all the intervals containing p have the same color. We also prove the corresponding result about online coloring a family of wedges (quadrants) in the plane that are the translates of a given fixed wedge. These results contrast the results of the first and third author showing that in the quasi-online setting 12 colors are enough to color wedges (independent of N and k). We also consider quasi-online coloring of intervals. In all cases we present efficient coloring algorithms.