Polychromatic Colorings of Unions of Geometric Hypergraphs

12/06/2021
by   Vera Chekan, et al.
0

We consider the polychromatic coloring problems for unions of two or more geometric hypergraphs on the same vertex sets of points in the plane. We show, inter alia, that the union of bottomless rectangles and horizontal strips does in general not allow for polychromatic colorings. This strengthens the corresponding result of Chen, Pach, Szegedy, and Tardos [Random Struct. Algorithms, 34:11-23, 2009] for axis-aligned rectangles, and gives the first explicit (not randomized) construction of non-2-colorable hypergraphs defined by axis-parallel rectangles of arbitrarily large uniformity.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset