Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 7

Problem 706

Statement. Let $L(r)$ be such that if $G$ is a graph formed by taking a finite set of points $P$ in $\mathbb{R}^2$ and some set $A\subset (0,\infty)$ of size $r$ , where the vertex set is $P$ and there is an edge between two points if and only if their distance is a member of $A$ , then $\chi(G)\leq L(r)$ .

Estimate $L(r)$ . In particular, is it true that $L(r)\leq r^{O(1)}$ ?

Status. Open.

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

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.

Linked from (37)

Graph Coloring discrete_geometry/erdos_1981_applications_graph_theory_combinatorial_methods_number Unit distance graphs in the plane, p. 142: Wormald's 4-chromatic girth-5 example, the girth conjecture, and the growth of α₂(r)Graph Coloring graph_coloring/akhiiarov_2025_lower_bounds_independence_numbers_distance_graphs Theorem 5 (pp. 6--7): a greedy (Varshamov--Gilbert) lower bound |V_n(k_{-1},k_0,k_1)|/d on the independence number of the ternary one-distance graph Theorem 6 (pp. 7--8): a union of block (Ahlswede--Khachatrian) constructions indexed by a greedy family bounds m(n, k_{-1}, k_0, k_1, t) from below Theorem 7 (p. 8): the union of block constructions over a greedy family with a larger threshold s, thinned of forbidden pairs Theorem 8 (p. 9): for even n and k_1 + k_{-1} and odd t, m(n, k_{-1}, k_0, k_1, t) >= C(n/2, (k_1+k_{-1})/2) C(k_1+k_{-1}, k_1)graph_coloring/berdnikov_2014_chromatic_number_euclidean_space_two_forbidden Definition (p. 791): the distance graph G(V; a_1, ..., a_k) and the bound chi(R^n; a_1, ..., a_k) >= chi(G(V; a_1, ..., a_k))Lemma (p. 791): the pair graphs of a 2k-distance graph have chromatic numbers with product at least |V|/alpha(G)Table (p. 793): two-distance chromatic bounds for R^n along subsequences, k = 2 and 3 Theorem (p. 791): exponential independence ratios for 2k-distance graphs give, along a subsequence of dimensions, two-distance chromatic bounds (zeta_2k^(1/k) + o(1))^n graph_coloring/berdnikov_2016_estimate_chromatic_number_euclidean_space_several Theorem 2 (p. 783): the bound (Bk)^(Cn) for every positive C < 1/3, all n and all k graph_coloring/berdnikov_2018_chromatic_numbers_distance_graphs_several_forbidden Corollary (p. 80): exponential growth rate of clique-free distance graphs is at least (Bk)^C Theorem 1 (p. 80): clique-free distance graphs with k forbidden distances, k at most Kn^A Theorem 2 (p. 80): clique-free distance graphs with k forbidden distances, all n and k graph_coloring/chybowskasokol_2023_coloring_distance_graphs_plane graph_coloring/exoo_2019_6_chromatic_two_distance_graph_plane Claim 2.1 (p. 3): the 205-vertex {1,2}-graph G has exactly 18 5-colorings Claim 2.2 (p. 3): in every 5-coloring of the 214-vertex {1,2}-graph H, the vertices A and B at distance 5 share a color Theorem 1.4 (p. 2): χ({1,2}) >= 6 graph_coloring/goncalves_2025_sphere_packings_euclidean_space_forbidden_distances graph_coloring/gorskaya_2009_estimating_chromatic_numbers_euclidean_space_convex Table of Section 5 (p. 797): zeta_k = e^{S_{20,k}} for k = 2,...,20 graph_coloring/naslund_2023_chromatic_number_r_n_multiple_forbidden Problem 4 (p. 16): is the m-distance chromatic number of the plane at least C g^(-1)(m) for some C > 1?Theorem 1 (p. 2): the m-distance chromatic number of R^n is at least (Γ_χ sqrt(m+1) + o(1))^n Theorem 2 (p. 3): colorings of R^n with distance set A_m and no monochromatic (k+1)-clique need (Γ_χ sqrt((m+1)/k) + o(1))^n colors Theorem 3 (p. 3): partition-rank lower bound for χ_k(R^n, A_m) by a truncated theta quotient Theorem 4 (p. 3): the truncated theta quotient is at least Γ_χ sqrt(1/γ) for 0 < γ < 1 graph_coloring/parts_2020_small_6_chromatic_two_distance_graph Theorem (p. 4, unnumbered): χ((√5+1)/2) >= 6, via a 31-vertex graph graph_coloring/parts_2023_more_certainty_coloring_plane_forbidden_distance

Graph