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.
vertex count edge count discovery
date 553 2840 Jul. 4, 2019 529 2630 Jul. 4, 2019 525 2605 Jul. 16, 2019 510 2508 Aug. 3,
2019 510 2502 prior to Mar. 7, 2020 509 2442 prior to Mar. 7, 2020
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
The Parts graphs are implemented in the Wolfram Language as GraphData "PartsGraph509" ]
etc.
See also de Grey Graphs ,
Hadwiger-Nelson Problem ,
Heule Graphs ,
Mixon
Graphs ,
Unit-Distance Graph
Explore with Wolfram|Alpha
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 . 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.
Cite this as:
Weisstein, Eric W. "Parts Graphs." From
MathWorld https://mathworld.wolfram.com/PartsGraphs.html
Subject classifications
). 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.)
