Parts Graphs

The Parts graphs are a set of unit-distance graphs with chromatic number five derived by Jaan Parts in 2019-2020 (Parts 2020a). 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 Parts graphs are summarized in the following table and illustrated above.

Additional graphs on 16, 31, and 199 nodes are also associated with Parts (2020b). The 31-node graph gives a small 6-chromatic graphs with exactly two edge lengths (1 and the golden ratio ). It can be obtained by combining one copy of the 16-vertex graph with another obtained by rotating about one of the first copy's vertices. (Note that note that both the 16- and 31-node graphs are edge-edge and edge-vertex degenerate.)

The Parts graphs will be implemented in a future version of the Wolfram Language as GraphData["PartsGraph509"] etc.

REFERENCES

--. "Hadwiger-Nelson Problem." https://asone.ai/polymath/index.php?title=Hadwiger-Nelson_problem.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.

Parts, J. Polymath16 comments. https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans/#comment-23713, https://dustingmixon.wordpress.com/2019/07/08/polymath16-thirteenth-thread-bumping-the-deadline/#comment-23814, and https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans/#comment-23713.

Parts, J. "Graph Minimization, Focusing on the Example of 5-Chromatic Unit-Distance Graphs in the Plane." Geombinatorics 29, No. 4, 137-166, 2020a.

Parts, J. "A Small 6-Chromatic Two-Distance Graph in the Plane." 23 Oct 2020b. https://arxiv.org/abs/2010.12656.