未解決問題、組合せ論と離散数学, 幾何学、1950年に提起

ハドウィガー・ネルソン問題

未解決

ユークリッド平面の彩色数 $\chi(\mathbb{R}^2)$ 、すなわちユークリッド距離が $\|x - y\|_2 = 1$ であるどの2点も同じ色にならないように平面 $\mathbb{R}^2$ のすべての点を塗り分けるために必要な最小の色数を決定せよ。

研究の最前線 2026年時点

2026年現在、平面の彩色数は $5 \le \chi(\mathbb{R}^2) \le 7$ を満たす。下界 $\chi(\mathbb{R}^2) \ge 5$ はオーブリー・ド・グレイ（2018年）および独立にエクソーとイスマイレスク（2020年）によって確立され、既知の最小の $5$ -彩色単位距離グラフは $509$ 頂点である（パーツ、2020年）。可測彩色については $\chi_m(\mathbb{R}^2) \ge 5$ や関連する $\chi_m(\mathbb{R}^2) \ge 6$ の評価が研究されているが、 $\mathbb{R}^2$ 内に有限の $6$ -彩色単位距離グラフが存在するかどうかは未解決である。

既知の最良の結果

平面の彩色数は少なくとも $5$ である： $5 \le \chi(\mathbb{R}^2) \le 7$ （オーブリー・ド・グレイ、2018年）。
$\mathbb{R}^2$ で既知の最小の $5$ -彩色単位距離グラフは $509$ 頂点である（ヒューレの $510$ 頂点グラフに続くヤーン・パーツの2020年の結果）。

使われた手法と限界

手法	達成したこと	限界
代数的単位距離格子とSATソルバー	多数のモーザー・スピンドルを含む $\mathbb{Q}[\sqrt{3}, \sqrt{11}]$ の密な部分グラフを埋め込み、すべての $4$ 彩色が阻止されることをSATソルバーで検証して $\chi(\mathbb{R}^2) \ge 5$ を証明した。	$5$ 彩色に対しては、 $\mathbb{R}^2$ の単位距離グラフの平均次数が小さすぎるため、天文学的な頂点数なしに $5$ 彩色可能性を排除することが困難である。
可測彩色に対する調和解析と半正定値計画法	ベッセル関数を用いて $\mathbb{R}^2$ の可測独立集合の最大密度を評価し、 $\chi_m(\mathbb{R}^2) \ge 5$ を証明した。	選択公理を用いて構成される非可測な $5$ 彩色や $6$ 彩色を排除することはできない。

未解決の問い

ユークリッド平面の彩色数 $\chi(\mathbb{R}^2)$ は $5$ 、 $6$ 、 $7$ のいずれに等しいか。
$\chi(\mathbb{R}^2)$ の値は選択公理やZFCの拡張公理に依存するか。

参考文献

Aubrey D. N. J. de Grey (2018). The chromatic number of the plane is at least 5 · arXiv:1804.02385
Alexander Soifer (2009). The Mathematical Coloring Book · DOI:10.1007/978-0-387-74642-5