哈德維格-納爾遜問題
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/2/25/Hadwiger-Nelson_problem.png)
哈德維格-納爾遜問題(英語:Hadwiger–Nelson problem),是指在平面上為每點填色,最少要多少種顏色,才能使若兩點距離為1,其顏色必定不相同呢?用圖論的語言可這樣敍述:設G為圖,G的頂點是平面上的所有點,兩個頂點相鄰若且唯若它們在平面上的距離為1,求G的點色數。這個問題等於求任意G的有限子集的最大點色數。[1]
這個問題的下界是5,上界是7。
只有三種顏色無法完成的證明如下:平面上任取一點A,設其顏色為x,以其為圓心,分別以1和為半徑做圓。在半徑的圓上任取一點B,以其為圓心1為半徑做圓,交以A為圓心1為半徑的圓與C和D,則C與D的距離為1,所以A、C、D顏色必須各不相同,設C、D的顏色分別為y、z。B、C、D的顏色也必須各不相同,所以B的顏色只能是x,所以以A為圓心為半徑的圓上所有的點的顏色都必須為x,在其上選擇兩個相距為1的點,它們的顏色相同,與題設矛盾。
另一方面,將平面劃成以外接圓直徑略少於1的正六邊形密鋪,以七種顏色填上,使得一個正六邊形和相鄰的六個正六邊形的顏色不同。這樣的密舖符合距離為1的點顏色不相同,所以上界是7。
歷史
這個問題由E. Nelson在1950年提出,馬丁·加德納在1960年的《科學美國人》雜誌公開發表。Hugo Hadwiger在1945年曾發表一個相關的定理[2][3]。
2018年,業餘數學家兼生物學家奧布里·大衛·尼古拉斯·傑士伯·德格雷找到了[4]一個1581個點的、不可4染色的、所有邊長度為1的圖。其證明是基於計算機輔助的。
變化
相關連結
參考資料
- ^ 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.
- ^ Hadwiger, Hugo (1945). "Überdeckung des euklidischen Raumes durch kongruente Mengen". Portugal. Math. 4: 238–242.
- ^ Jensen, Tommy R.; Toft, Bjarne (1995). Graph Coloring Problems. Wiley-Interscience Series in Discrete Mathematics and Optimization, 150–152.
- ^ de Grey, Aubrey D. N. J. The chromatic number of the plane is at least 5. arXiv:1804.02385 [math]. 2018-04-07 [2018-04-18]. (原始內容存檔於2021-01-14).
- ^ Croft, Hallart T.; Falconer, Kenneth J.; Guy, Richard K. (1991). Unsolved Problems in Geometry. Springer-Verlag, Problem G10.
參考文獻
- Chilakamarri, K. B. (1993). "The unit-distance graph problem: a brief survey and some new results". Bull Inst. Combin. Appl. 8: 39–60.