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 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 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 note that both the 16- and 31-node graphs are edge-edge and edge-vertex degenerate.)
). 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.)
