Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10327193 | Computational Geometry | 2012 | 13 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Balázs Keszegh,