主題
Search

Hadwiger-Nelson 問題


Hadwiger-Nelson 問題 詢問平面的色數,即為平面著色所需的最少顏色數,使得平面上任意兩個距離為 1 的點顏色都不同。Nelson 在 1950 年首次討論(但未發表)了這個問題 (Soifer 2008, de Grey 2018)。自那時起,已知確切答案為 4、5、6 或 7,下界由單位距離圖(例如 Moser spindleGolomb graph)(它們的色數均為 4)給出,上界由全等正六邊形平鋪平面(可以分配七種顏色,以某種模式分隔所有相同顏色的瓷磚對,使其距離大於其直徑)給出,這最早由 Isbell 在 1950 年觀察到,並由 Hadwiger 在不同背景下討論過 (1945; Soifer 2008, de Grey 2018)。

第一個色數大於等於 5 的單位距離圖由 de Grey (2018) 構造。其中最小的一個是從一個更大的例子簡化而來的,是一個具有 1581 個頂點的圖,這裡稱為 de Grey 圖。這個圖的存在確立了平面的色數為 5、6 或 7。在 de Grey 的圖發表之後,Dustin Mixon、Marijn Heule 和 Jaan Parts 在隨後的幾天、幾周、幾個月和幾年裡發現了從中匯出的更小的非 4-可著色單位距離圖。


另請參閱

de Grey 圖, 四色定理, Golomb 圖, Hadwiger 猜想, Hadwiger 數, Heule 圖, Mixon 圖, Parts 圖, Moser Spindle, 單位距離圖

使用 探索

參考文獻

Chilakamarri, K. B. "單位距離圖問題:簡要綜述和一些新結果。" Bull Inst. Combin. Appl. 8, 39-60, 1993.Coulson, D. "關於平面平鋪的色數。" J. Austral. Math. Soc. 77, 191-196, 2004.Coulson, D. (2002), "省略距離 1 的 3 空間 15 著色", Discrete Math. 256: 83-90, 2002. Croft, H. T.; Falconer, K. J.; 和 Guy, R. K. 幾何中的未解決問題。 中的問題 G10。紐約:Springer-Verlag, 1991.de Bruijn, N. G. 和 Erdős, P. "無限圖的著色問題和關係理論中的問題。" Nederl. Akad. Wetensch. Proc. Ser. A 54, 371-373, 1951.de Grey, A. D. N. J. "平面的色數至少為 5。" Geombinatorics 28, No. 1, 18-31, 2018.Erdős, P.; Harary, F.; 和 Tutte, W. T. "關於圖的維度。" Mathematika 12, 118-122, 1965.Exoo, G. 和 Ismailescu, D. "平面的色數至少為 5:一個新的證明。" Disc. Comput. Geom. 64, 216-226, 2020.Gardner, M. "數學遊戲。" Sci. Amer. 203, 180, 1960.Hadwiger, H. "歐幾里得空間透過全等集的覆蓋。" Portugal. Math. 4, 238-242, 1945.Hadwiger, H. "未解決的問題 No. 40。" Elem. Math. 16, 103-104, 1961.Heule, M. J. H. "計算色數為 5 的小型單位距離圖。" Geombinatorics 28, 32-50, 2018.Jensen, T. R. 和 Toft, B. 圖著色問題。 紐約:Wiley, pp. 150-152, 1995.Lamb, E. "數十年之久的圖問題被業餘數學家解決。" Quanta Mag. 2018 年 4 月 17 日。 https://www.quantamagazine.org/decades-old-graph-problem-yields-to-amateur-mathematician-20180417/.Mixon, D. G. "Polymath16,第一個主題:簡化 De Grey 的圖。" 2018 年 4 月 14 日。 https://dustingmixon.wordpress.com/2018/04/14/polymath16-first-thread-simplifying-de-greys-graph/.Parts, J. "圖的最小化,重點是在平面中 5 色單位距離圖的例子。" Geombinatorics 29, No. 4, 137-166, 2020.PolyMath. "Hadwiger-Nelson 問題。" http://michaelnielsen.org/polymath1/index.php?title=Hadwiger-Nelson_problem.Shelah, S. 和 Soifer, A. "選擇公理與平面的色數。" J. Combin. Th., Ser. A 103, 387-391, 2003.Soifer, A. 數學著色書:著色的數學及其創造者的多彩生活。 紐約:Springer, 2008.Soifer, A. "我最喜歡的數學開放問題的突破:平面的色數。" https://www.cs.umd.edu/~gasarch/BLOGPAPERS/soifer.pdf.

在 中引用

Hadwiger-Nelson 問題

請這樣引用

Weisstein, Eric W. "Hadwiger-Nelson 問題。" 來自 Web 資源。 https://mathworld.tw/Hadwiger-NelsonProblem.html

學科分類