Hadwiger-Nelson 问题

Hadwiger-Nelson 问题询问平面的色数，即为平面着色所需的最少颜色数，使得平面上任意两个距离为 1 的点颜色都不同。Nelson 在 1950 年首次讨论（但未发表）了这个问题 (Soifer 2008, de Grey 2018)。自那时起，已知确切答案为 4、5、6 或 7，下界由单位距离图（例如 Moser spindle 和 Golomb graph）（它们的色数均为 4）给出，上界由全等正六边形平铺平面（可以分配七种颜色，以某种模式分隔所有相同颜色的瓷砖对，使其距离大于其直径）给出，这最早由 Isbell 在 1950 年观察到，并由 Hadwiger 在不同背景下讨论过 (1945; Soifer 2008, de Grey 2018)。

第一个色数大于等于 5 的单位距离图由 de Grey (2018) 构造。其中最小的一个是从一个更大的例子简化而来的，是一个具有 1581 个顶点的图，这里称为 de Grey 图。这个图的存在确立了平面的色数为 5、6 或 7。在 de Grey 的图发表之后，Dustin Mixon、Marijn Heule 和 Jaan Parts 在随后的几天、几周、几个月和几年里发现了从中导出的更小的非 4-可着色单位距离图。

另请参阅

de Grey 图, 四色定理, Golomb 图, Hadwiger 猜想, Hadwiger 数, Heule 图, Mixon 图, Parts 图, Moser Spindle, 单位距离图

使用探索

更多尝试

参考文献

Chilakamarri, K. B. "单位距离图问题：简要综述和一些新结果。" Bull Inst. Combin. Appl. 8, 39-60, 1993.Coulson, D. "关于平面平铺的色数。" J. Austral. Math. Soc. 77, 191-196, 2004.Coulson, D. (2002), "省略距离 1 的 3 空间 15 着色", Discrete Math. 256: 83-90, 2002. Croft, H. T.; Falconer, K. J.; 和 Guy, R. K. 几何中的未解决问题。 中的问题 G10。纽约：Springer-Verlag, 1991.de Bruijn, N. G. 和 Erdős, P. "无限图的着色问题和关系理论中的问题。" Nederl. Akad. Wetensch. Proc. Ser. A 54, 371-373, 1951.de Grey, A. D. N. J. "平面的色数至少为 5。" Geombinatorics 28, No. 1, 18-31, 2018.Erdős, P.; Harary, F.; 和 Tutte, W. T. "关于图的维度。" Mathematika 12, 118-122, 1965.Exoo, G. 和 Ismailescu, D. "平面的色数至少为 5：一个新的证明。" Disc. Comput. Geom. 64, 216-226, 2020.Gardner, M. "数学游戏。" Sci. Amer. 203, 180, 1960.Hadwiger, H. "欧几里得空间通过全等集的覆盖。" Portugal. Math. 4, 238-242, 1945.Hadwiger, H. "未解决的问题 No. 40。" Elem. Math. 16, 103-104, 1961.Heule, M. J. H. "计算色数为 5 的小型单位距离图。" Geombinatorics 28, 32-50, 2018.Jensen, T. R. 和 Toft, B. 图着色问题。 纽约：Wiley, pp. 150-152, 1995.Lamb, E. "数十年之久的图问题被业余数学家解决。" Quanta Mag. 2018 年 4 月 17 日。 https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/.Mixon, D. G. "Polymath16，第一个主题：简化 De Grey 的图。" 2018 年 4 月 14 日。 https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread-simplifying-de-greys-graph/.Parts, J. "图的最小化，重点是在平面中 5 色单位距离图的例子。" Geombinatorics 29, No. 4, 137-166, 2020.PolyMath. "Hadwiger-Nelson 问题。" http://michaelnielsen.org/polymath1/index.php?title=Hadwiger-Nelson_problem.Shelah, S. 和 Soifer, A. "选择公理与平面的色数。" J. Combin. Th., Ser. A 103, 387-391, 2003.Soifer, A. 数学着色书：着色的数学及其创造者的多彩生活。 纽约：Springer, 2008.Soifer, A. "我最喜欢的数学开放问题的突破：平面的色数。" https://www.cs.umd.edu/~gasarch/BLOGPAPERS/soifer.pdf.