Heule 图是由 Marijn Heule 于 2018 年 4 月至 2918 年 7 月从 1581 个顶点的 de Grey 图 (Heule 2018) 推导出来的一组单位距离图，其色数为 5。它们提供了一些已知的最小例子，这些例子确定了Hadwiger-Nelson 问题（即平面的色数）的解为 5、6 或 7。这个 529 个顶点的图是在大约 100,000 CPU 小时的计算后发现的 (Heule 2019)。
Jaan Parts 发现了其他小型图，并在本文中称为 Parts 图。
Heule 图示于上方，并在下表中进行了总结。
| 顶点计数 | 边计数 | 发现日期 |
| 874 | 4461 | Apr. 14, 2018 |
| 826 | 4273 | Apr. 16, 2018 |
| 803 | 4144 | Apr. 30, 2018 |
| 633 | 3166 | May 6, 2018 |
| 610 | 3000 | May 14, 2018 |
| 553 | 2722 | May 30, 2018 |
| 529 | 2670 | Jul. 1, 2019 |
| 517 | 2579 | Jul. 28, 2019 |
| 510 | 2504 | Aug. 8, 2019 |
Heule 图在 Wolfram Language 中实现为GraphData["HeuleGraph510"] 等。
参见
de Grey 图、
Hadwiger-Nelson 问题、
Heule 纺锤、
Mixon 图、
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. May 6, 2018. https://dustingmixon.wordpress.com/2018/05/05/polymath16-fourth-thread-applying-the-probabilistic-method/#comment-4316.Heule, M. May 14, 2018. https://dustingmixon.wordpress.com/2018/05/10/polymath16-fifth-thread-human-verifiable-proofs/#comment-4465.Heule, M. J. H. "Computing Small Unit-Distance Graphs with Chromatic Number 5." Geombinatorics 28, 32-50, 2018.Heule, M. "Computing Small Unit-Distance Graphs with Chromatic Number 5." 30 May 2018. https://arxiv.org/abs/1805.12181.Heule, M. "Computing a Smaller Unit-Distance Graph with Chromatic Number 5 via Proof Trimming." 1 Jul 2019. https://arxiv.org/abs/1907.00929.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. "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.Soifer, A. "Marienus Johannes Hendrikus 'Marijn' Heule." Ch. 53 in The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, 2nd ed. New York: Springer, pp. 675-692, 2024.
请引用为
Weisstein, Eric W. "Heule 图。" 来自 Web 资源。 https://mathworld.net.cn/HeuleGraphs.html
学科分类
