查看“︁哈德維格-納爾遜問題”︁的源代码

[[File:Hadwiger-Nelson problem.png|right]]

'''哈德維格-納爾遜問題'''（{{lang-en|Hadwiger–Nelson problem}}），是指在[[平面 (数学)|平面]]上為每點填色，最少要多少種顏色，才能使若兩點距離為1，其顏色必定不相同呢？用[[圖論]]的語言可這樣敍述：設G為[[圖]]，G的頂點是平面上的所有點，兩個頂點相鄰若且唯若它們在平面上的距離為1，求G的點色數。這個問題等於求任意G的有限子集的最大[[點色數]]。<ref>de Bruijn, N.G.; [[保羅·艾狄胥|Erdős, P]]. (1951). "A colour problem for infinite graphs and a problem in the theory of relations". Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373.</ref>

這個問題的下界是5，上界是7。

只有三種顏色無法完成的證明如下：平面上任取一點A，設其顏色為x，以其為圓心，分別以1和<math>\sqrt 3</math>為半徑做圓。在半徑<math>\sqrt 3</math>的圓上任取一點B，以其為圓心1為半徑做圓，交以A為圓心1為半徑的圓與C和D，則C與D的距離為1，所以A、C、D顏色必須各不相同，設C、D的顏色分別為y、z。B、C、D的顏色也必須各不相同，所以B的顏色只能是x，所以以A為圓心<math>\sqrt 3</math>為半徑的圓上所有的點的顏色都必須為x，在其上選擇兩個相距為1的點，它們的顏色相同，與題設矛盾。

另一方面，將平面劃成以外接圓直徑略少於1的正六邊形[[密鋪]]，以七種顏色填上，使得一個正六邊形和相鄰的六個正六邊形的顏色不同。這樣的密舖符合距離為1的點顏色不相同，所以上界是7。

==歷史==
這個問題由E. Nelson在1950年提出，[[馬丁·加德納]]在1960年的《[[科學美國人]]》雜誌公開發表。Hugo Hadwiger在1945年曾發表一個相關的定理<ref>Hadwiger, Hugo (1945). "Überdeckung des euklidischen Raumes durch kongruente Mengen". Portugal. Math. 4: 238–242.</ref><ref>Jensen, Tommy R.; Toft, Bjarne (1995). Graph Coloring Problems. Wiley-Interscience Series in Discrete Mathematics and Optimization, 150–152.</ref>。

2018年，业余数学家兼生物学家[[奥布里·大卫·尼古拉斯·杰士伯·德格雷]]找到了<ref>{{Cite journal|title=The chromatic number of the plane is at least 5|url=http://arxiv.org/abs/1804.02385|last=de Grey|first=Aubrey D. N. J.|date=2018-04-07|journal=arXiv:1804.02385 [math]|access-date=2018-04-18|archive-date=2021-01-14|archive-url=https://web.archive.org/web/20210114174329/https://arxiv.org/abs/1804.02385|dead-url=no}}</ref>一个1581个点的、不可4染色的、所有边长度为1的图。其证明是基于计算机辅助的。

==變化==
* 三維空間：上界15，下界6
* 限制某種顏色的集的性質。例如要求每種顏色的集都是[[勒贝格可测]]的，則下界為5。<ref>Croft, Hallart T.; Falconer, Kenneth J.; Guy, Richard K. (1991). Unsolved Problems in Geometry. Springer-Verlag, Problem G10.</ref>

== 相關連結 ==
* [[四色定理]]

== 參考資料 ==
{{Reflist|2}}

== 參考文獻 ==
* Chilakamarri, K. B. (1993). "The unit-distance graph problem: a brief survey and some new results". Bull Inst. Combin. Appl. 8: 39–60.

[[Category:数学中未解决的问题]]
[[Category:图染色]]