Proper Coloring of Geometric Hypergraphs
Balázs Keszegh, Dömötör Pálvölgyi · Discrete & Computational Geometry · 2019
We study whether for a given planar family $${\mathcal {F}}$$ there is an m such that any finite set of points can be 3-colored so that any member of $${\mathcal {F}}$$ that contains at least m points contains two points with different colors. We conjecture that if $${\mathcal {F}}$$ is a family of pseudo-disks, then such an m exists. We prove this in the special case when $${\mathcal {F}}$$ is the family of all homothetic copies of a given convex polygon. We also study the problem in higher dimensions.