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.

اخر الاخبار

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

قسم الصناعات والحرف الفنية ينفذ أعمالًا تطويرية في جامعة الكفيل

قسم الشؤون الطبية يناقش تحضيراته لحفل التخرج المركزي لطالبات الجامعات العراقية العاشر

مركز الكفيل للإعلان والتسويق يباشر تنفيذ الأعمال الطباعية لحفل تخرج طالبات الجامعات العراقية العاشر

قسم رعاية الصحن يهيئ الأماكن المخصصة لفعاليات حفل تخرج طالبات الجامعات العراقية العاشر

المزيد

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

خصوصا مع تقدم السن.. 6 سلوكيات يومية قد تدمّر صحتك

فاكهة خضراء.. علاج طبيعي فعّال للإمساك واضطرابات الهضم

روسيا تبدأ أولى التجارب السريرية للقاح واعد ضد السرطان

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

المزيد

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

رصد نوع نادر من القطط في تايلاند للمرة الأولى منذ عقود

روسيا تخطط لإقامة محطة نووية في القمر خلال العقد المقبل

كيف قاد إيلون ماسك حملة "غروك" لاختراق عرش الذكاء الاصطناعي

ألتمان: الذكاء الاصطناعي سيتجاوز البشر في 2026 !

المزيد

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

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