Heule Graphs
Heule graphs are a set of unit-distance graphs with chromatic number five derived by Marijn Heule in April 2018 to July 2918 from the 1581-vertex de Grey Graph (Heule 2018). They provide some of the smallest known examples that establish the solution to the Hadwiger-Nelson problem (i.e., the chromatic number of the plane) as 5, 6, or 7. The 529-vertex graph was found after roughly 100,000 CPU-hours of computation (Heule 2019).
Additional small graphs were found by Jaan Parts and are called Parts graphs in this work.
The Heule graphs are illustrated above and summarized in the following table.
| vertex count |
edge count |
discovery date |
| 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 |
The Heule graphs are implemented in the Wolfram Language as GraphData["HeuleGraph510"] etc.
REFERENCES
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.
