2011/05/01 by Keszegh, Balázs · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1105.0169
We prove lower and upper bounds for the chromatic number of certain hypergraphs defined by geometric regions. This problem has close relations to conflict-free colorings. One of the most interesting type of regions to consider for this problem is that of the axis-parallel rectangles. We completely solve the problem for a special case of them, for bottomless rectangles. We also give an almost complete answer for half-planes and pose several open problems. Moreover we give efficient coloring algorithms.