哈德维格-纳尔逊问题
哈德维格-纳尔逊问题（英语：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.