Hadwiger-Nelson Problem

The Hadwiger-Nelson problem asks for the chromatic number of the plane, i.e., the minimum number of colors needed to color the plane if no two points at unit distance one from one another are given the same color. The problem was first discussed (though not published) by Nelson in 1950 (Soifer 2008, de Grey 2018). Since that time, the exact answer was known to be 4, 5, 6, or 7, with the lower bound provided by unit-distance graphs such as the Moser spindle and Golomb graph (both of which have chromatic number 4), and the upper bound by the tiling of the plane by congruent regular hexagons tiling the plane (which can be assigned seven colors in a pattern that separates all same-colored pairs of tiles by more than their diameter), as first observed by Isbell in 1950 and discussed in different context by Hadwiger (1945; Soifer 2008, de Grey 2018).

The first unit-distance graphs with chromatic number of five or larger was constructed by de Grey (2018). The smallest of these was reduced from a larger example to a graph on 1581 vertices, here called the de Grey graph. The existence of this graph established that the chromatic number of the plane is 5, 6, or 7. Following the publication of de Grey's graph, smaller non-4-colorable unit-distance graphs derived from it were discovered by Dustin Mixon, Marijn Heule, and Jaan Parts in the ensuing days, weeks, months, and years.

---

REFERENCES

Chilakamarri, K. B. "The Unit-Distance Graph Problem: A Brief Survey and Some New Results." Bull Inst. Combin. Appl. 8, 39-60, 1993.

Coulson, D. "On the Chromatic Number of Plane Tilings." J. Austral. Math. Soc. 77, 191-196, 2004.

Coulson, D. (2002), "A 15-colouring of 3-space omitting distance one", Discrete Math. 256: 83-90, 2002.

Croft, H. T.; Falconer, K. J.; and Guy, R. K. Problem G10 in Unsolved Problems in Geometry. New York: Springer-Verlag, 1991.

de Bruijn, N. G. and Erdős, P. "A Colour Problem for Infinite Graphs and a Problem in the Theory of Relations." Nederl. Akad. Wetensch. Proc. Ser. A 54, 371-373, 1951.

de Grey, A. D. N. J. "The Chromatic Number of the Plane Is at Least 5." Geombinatorics 28, No. 1, 18-31, 2018.

Erdős, P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.

Exoo, G. and Ismailescu, D. "The Chromatic Number of the Plane Is at Least 5: A New Proof." Disc. Comput. Geom. 64, 216-226, 2020.

Gardner, M. "Mathematical Games." Sci. Amer. 203, 180, 1960.

Hadwiger, H. "Überdeckung des euklidischen Raumes durch kongruente Mengen." Portugal. Math. 4, 238-242, 1945.

Hadwiger, H. "Ungelöste Probleme No. 40." Elem. Math. 16, 103-104, 1961.

Heule, M. J. H. "Computing Small Unit-Distance Graphs with Chromatic Number 5." Geombinatorics 28, 32-50, 2018.

Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, pp. 150-152, 1995.

Lamb, E. "Decades-Old Graph Problem Yields to Amateur Mathematician." Quanta Mag. Apr. 17, 2018.

 https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/.Mixon, D. G. "Polymath16, First Thread: Simplifying De Grey's Graph." 14 Apr 2018.

 https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread-simplifying-de-greys-graph/.Parts, J. "Graph Minimization, Focusing on the Example of 5-Chromatic Unit-Distance Graphs in the Plane." Geombinatorics 29, No. 4, 137-166, 2020.

PolyMath. "Hadwiger-Nelson Problem." http://michaelnielsen.org/polymath1/index.php?title=Hadwiger-Nelson_problem.Shelah, S. and Soifer, A. "Axiom of Choice and Chromatic Number of the Plane." J. Combin. Th., Ser. A 103, 387-391, 2003.

Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, 2008.Soifer, A. "Breakthrough in My Favorite Open Problem of Mathematics: Chromatic Number of the Plane." https://www.cs.umd.edu/~gasarch/BLOGPAPERS/soifer.pdf.

اخر الاخبار

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

العتبة العباسية المقدسة تشارك بأكثر من 750 إصدارًا في معرض بغداد الدولي للكتاب

تيمنًا بذكرى ولادة الصادقَين (صلوات الله عليهما) شعبة التوجيه النسوي تنظم مسابقة ميدانية لزائرات مرقد أبي الفضل العباس (عليه السلام)

المجمع العلمي ينظّم أنشطةً قرآنية في محافظتي كربلاء والديوانية

العتبة العباسية المقدسة تختتم فعاليات مهرجان رحمة للعالمين الدولي الأوَّل

المزيد

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

الأطعمة الحارة.. "سر صغير" يغير صحة قلبك وعقلك

وباء صامت.. الملايين حول العالم مصابون بالسكري دون أن يعلموا !

لماذا ينصح بتناول تفاحة يوميا؟

8 فواكه طبيعية تمنحك نوما هنيئا.. وتخلصك من الأرق

المزيد

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

ثلاث علامات على وجود مشاكل خطيرة في محرك السيارة ؟

ماذا نعرف عن اللقاح الروسي ضد السرطان؟

مركبة فضاء تعثر على دليل عن وجود حياة قديمة على المريخ

لتدريب الذكاء الاصطناعي.. الصين تخطط لإنشاء شبكة حوسبة موحدة

المزيد

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

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