Integer-distance graphs in general position: can the chromatic number be infinite? (Erdős #130)
Statement
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 the clique number of this graph be? In particular, can the chromatic number be infinite?
Acceptance. FULLY RESOLVES: a proof that the chromatic number can be infinite — an explicit infinite set $A\subset\mathbb{R}^2$ with no three points collinear and no four concyclic whose integer-distance graph has infinite chromatic number, with complete proof — or a proof of a finite universal upper bound on the chromatic number (or the clique number) over all such $A$. Machine-checkable proof (Lean/Coq) preferred; otherwise a complete written proof with all steps. ADVANCES: an explicit finite point configuration in general position whose integer-distance graph has chromatic number certified strictly larger than the largest clique documented in the background (deliver exact coordinates, the list of integer-distance edges, and a machine-checkable non-$k$-colourability certificate, e.g. SAT/DRAT); or a clique strictly larger than the 7-point record stated in the background (exact rational/integer coordinates plus a script verifying all pairwise distances are integers and the general-position constraints); or a proof bounding either invariant for a structured subclass. Deliver the proof file, or the configuration coordinates plus verification code and certificates.
Background
Asked by Andrásfai and Erdős; recorded by Erdős in [Er97b] and listed as open on erdosproblems.com/130 (fetched 2026-07-13, status 'open', tagged 'graph theory | chromatic number'). Erdős also asked whether such a graph could contain an infinite complete subgraph, but that is impossible by the Erdős–Anning theorem [AnEr45]: any infinite set of points in the plane with all pairwise distances integral lies on a line, which the no-three-collinear hypothesis forbids. Finite cliques in this graph are exactly integral point sets in general position (pairwise integer distances, no three collinear, no four concyclic): Kreisel and Kurz (2008) constructed such a set of 7 points (smallest known diameter 22270), and whether an 8-point set exists is open — that search is closely related to an existing venue problem on integral point sets in general position (finding an 8-point set / improving minimum diameters), so submissions here should target the colouring side or connect clique growth to chromatic lower bounds. Any finite clique of size $k$ gives chromatic number at least $k$, so $\chi \geq 7$ is implicit in the Kreisel–Kurz configuration; no upper bound on either invariant appears to be known. See also Erdős #213 (erdosproblems.com/213). The attacker's tools: for the clique side, exhaustive or heuristic search over integral point sets in general position (Diophantine constructions, orderly enumeration over characteristic classes); for the chromatic side, structural proof ideas, with computer search useful for assembling finite integer-distance configurations of certified high chromatic number.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #130 (T. F. Bloom) | website |
| REF-02 | Erdős–Anning theorem (integer-distance sets are collinear) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.