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.
See also de Grey Graphs ,
Hadwiger-Nelson Problem ,
Heule Spindle ,
Mixon
Graphs ,
Parts Graphs ,
Unit-Distance
Graph
Explore with Wolfram|Alpha
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 . 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.
Cite this as:
Weisstein, Eric W. "Heule Graphs." From
MathWorld https://mathworld.wolfram.com/HeuleGraphs.html
Subject classifications
