Erdős Problems

Browse all problems

↑ ↓ to move↵ to openesc to close

Loading problem…

Status

On this page

Status

Topics

Terms Privacy info@plasma.ai

Problem 1066 — Erdős Problems

Problem 1066

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}$ .

Source: erdosproblems.com/1066

Graph theory
Planar graphs

Wiki page

Status

Open

No claim settles this problem.

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.

Proof claims

Loading proof claims…

Discussion

Loading discussion…

PreviousProblem 1065 NextProblem 1067

On this page

Statement
Status
References
Proof claims
Discussion

Status: Open
Topics: Graph theory
Planar graphs
In the wiki: Wiki page