De Grey (2018) 发现了色数为 5 的单位距离图的首批示例，从而证明了哈德维格-纳尔逊问题（即平面的色数）的解至少为 5。De Grey 在修正后，将其最小示例的大小缩小到 1581 个顶点的 de Grey 图 (de Grey 2018)。
在最初的预印本发表几天后，Mixon (2018) 构建了一个类似的 1585 个顶点的图，从中移除 8 个顶点后，得到了一个更小的 1577 个顶点的图。这项工作将这些图称为 Mixon 图，如上所示。
更小的色数为 5 的单位距离图，这里称为 Heule 图和 Parts 图，是由 Marijn Heule 和 Jaan Parts 在 2018 年至 2020 年间从 de Grey 图计算得出的。截至 2022 年，其中最小的是 509 个顶点的 Parts 图 (Parts 2020)。
Mixon 图在 Wolfram 语言中以如下方式实现：GraphData["MixonGraph1577"] 等。
另请参阅
de Grey 图,
Golomb 图,
哈德维格-纳尔逊问题,
Heule 图,
Moser 纺锤,
Parts 图,
单位距离图
使用 探索
参考文献
de Grey, A. D. N. J. "The Chromatic Number of the Plane Is at Least 5." Geombinatorics 28, No. 1, 18-31, 2018.Heule, M. J. H. "Computing Small Unit-Distance Graphs with Chromatic Number 5." Geombinatorics 28, 32-50, 2018.Lamb, E. "Decades-Old Graph Problem Yields to Amateur Mathematician." Quanta Mag. Apr. 17, 2018. https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/.Mixon, D. G. "The Chromatic Number of the Plane Is at Least 5."Apr. 10, 2018. https://dustingmixon.wordpress.com/2018/04/10/the-chromatic-number-of-the-plane-is-at-least-5/.Mixon, D. G. "Polymath16, First Thread: Simplifying De Grey's Graph." 14 Apr 2018. https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread-simplifying-de-greys-graph/.Parts, J. "Graph Minimization, Focusing on the Example of 5-Chromatic Unit-Distance Graphs in the Plane." Geombinatorics 29, No. 4, 137-166, 2020.PolyMath. "Hadwiger-Nelson Problem." http://michaelnielsen.org/polymath1/index.php?title=Hadwiger-Nelson_problem.
请引用为
Weisstein, Eric W. “Mixon 图。” 来自 —— 资源。 https://mathworld.net.cn/MixonGraphs.html
主题分类
