Parts Graphs

The term "Parts graphs" is used in this work for 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 that the chromatic number of the plane, the quantity sought in the Hadwiger-Nelson problem, is 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 is a small 6-chromatic graph 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 both the 16- and 31-node graphs are edge-edge and edge-vertex degenerate.)

The 16-vertex Parts graph has graph crossing number 28 (E. Weisstein, Oct. 6, 2026).

The Parts graphs are implemented in the Wolfram Language as GraphData["PartsGraph509"] etc.

Explore with Wolfram|Alpha

More things to try:

--. "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.House of Graphs. Parts Graphs. Parts Graph 16, Parts Graph 31, and Parts Graph 199.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.Parts, J. Polymath16 comments. https://dustingmixon.wordpress.com/2019/03/23/polymath16-twelfth-thread-year-in-review-and-future-plans/#comment-23713 and https://dustingmixon.wordpress.com/2019/07/08/polymath16-thirteenth-thread-bumping-the-deadline/#comment-23814.Soifer, A. "Jaan Parts' Current World Record." Ch. 56 in The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, 2nd ed. New York: Springer, pp. 701-708, 2024.