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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

بمشاركة الأمين العام للعتبة العبّاسية المقدّسة.. موكب عزاء السادة الخَدَم يحيي ليلة عاشوراء

صحفيّون يشيدون بالتسهيلات الإعلامية التي تقدّمها العتبة العباسية المقدّسة خلال زيارة عاشوراء

أهالي كربلاء ينظّمون مسيرة الشموع الحسينية إحياءً لليلة العاشر من شهر المحرّم

عبر مجلس عزاء.. العتبة العباسية المقدّسة تحيي ليلة اليوم العاشر من المحرّم

المزيد

الآخبار الصحية

لهذا السبب.. إغلاق 25 مركزًا لعلاج الإدمان في مصر ؟

خلافا للاعتقاد الشائع.. علماء يكشفون أسرار بذور البطيخ ؟!

هذا ما يحدث لجسمك عند تناولك الطماطم بانتظام !

تعرف على أطعمة تسرّع "تعافي الجسم" من حروق الشمس

المزيد

الآخبار التكنلوجية

الثلوج تغطي الصحراء الأكثر جفافا في العالم!

بتلسكوب "ألما".. التقاط صورا غير مسبوقة لبدايات الكون !

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength