Parts Graphs
المؤلف:
Heule, M. J. H.
المصدر:
"Computing Small Unit-Distance Graphs with Chromatic Number 5." Geombinatorics 28
الجزء والصفحة:
...
30-3-2022
1910
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.
| 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 
). 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.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
