Problem 1066

../

---

Statement. Let $G$ be a graph given by $n$ points in $\mathbb{R}^2$, where any two distinct points are at least distance $1$ apart, and we draw an edge between two points if they are distance $1$ apart.

Let $g(n)$ be maximal such that any such graph always has an independent set on at least $g(n)$ vertices. Estimate $g(n)$, or perhaps $\lim \frac{g(n)}{n}$.

Status. Open.

Source. erdosproblems.com/1066, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #1066, https://www.erdosproblems.com/1066.

References.

• [Cs98] Csizmadia, G., On the independence number of minimum distance graphs. Discrete Comput. Geom. (1998), 179-187.
• [PaTo96] Pach, János and Tóth, Géza, On the independence number of coin graphs. Geombinatorics (1996), 30-33.
• [Po85] Pollack, R., Increasing the minimum distance of a set of points. J. Combin. Theory Ser. A (1985), 450.
• [Sw02] Swanepoel, Konrad J., Independence numbers of planar contact graphs. Discrete Comput. Geom. (2002), 649-670.

Formalization. None recorded.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• csizmadia_1998_independence_number_minimum_distance_graphs
• csizmadia_1998_independence_number_minimum_distance_graphs / lemma_1
• csizmadia_1998_independence_number_minimum_distance_graphs / remark_p187
• csizmadia_1998_independence_number_minimum_distance_graphs / theorem_p180
• swanepoel_2002_independence_numbers_planar_contact_graphs
• swanepoel_2002_independence_numbers_planar_contact_graphs / theorem_1
• swanepoel_2002_independence_numbers_planar_contact_graphs / theorem_2