TOPICS
Search

Heule Graphs


HeuleGraphs

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 countedge countdiscovery date
8744461Apr. 14, 2018
8264273Apr. 16, 2018
8034144Apr. 30, 2018
6333166May 6, 2018
6103000May 14, 2018
5532722May 30, 2018
5292670Jul. 1, 2019
5172579Jul. 28, 2019
5102504Aug. 8, 2019

The Heule graphs are implemented in the Wolfram Language as GraphData["HeuleGraph510"] etc.


See also

de Grey Graphs, Hadwiger-Nelson Problem, Mixon Graphs, Parts Graphs, Unit-Distance Graph

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

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.

Cite this as:

Weisstein, Eric W. "Heule Graphs." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HeuleGraphs.html

Subject classifications