Problem 130

Let $A\subset\mathbb{R}^2$ be an infinite set which contains no three points on a line and no four points on a circle. Consider the graph with vertices the points in $A$ , where two vertices are joined by an edge if and only if they are an integer distance apart.

How large can the chromatic number and clique number of this graph be? In particular, can the chromatic number be infinite?

Source: erdosproblems.com/130

Graph theory
Chromatic number

Wiki page

Status

Open

No claim settles this problem.

Open. Two pending partial claims answer the particular question yes: Lloyd.H's proof claim of 17 July 2026 on the site's proof-claims tab, recorded on its claim page (Lloyd H, 2026), and Star Fleet Math's Lean development, posted on its site by 15 July 2026, two days before Lloyd.H's claim, recorded on its claim page (Snyder, 2026) and linked by the formal-conjectures catalog as the statement's formal proof. The site's label is OPEN and its page credits neither.

AnEr45: Anning, Norman H. and Erdős, Paul, Integral distances. Bull. Amer. Math. Soc. (1945), 598-600.
Er97b: Erdős, Paul, Some old and new problems in various branches of combinatorics. Discrete Math. 165/166 (1997), 227--231, DOI 10.1016/S0012-365X(96)00173-2; item 5, printed p. 229 (PDF p. 3 of the publisher's open-archive file at that DOI): the Andrásfai--Erdős question in the statement's wording, with no result. Library home: Erdős 1997.

Problem 130

Status

Proof claims

Discussion