De Grey (2018) 發現了色數為 5 的單位距離圖的首批示例，從而證明了哈德維格-納爾遜問題（即平面的色數）的解至少為 5。De Grey 在修正後，將其最小示例的大小縮小到 1581 個頂點的 de Grey 圖 (de Grey 2018)。
在最初的預印本發表幾天後，Mixon (2018) 構建了一個類似的 1585 個頂點的圖，從中移除 8 個頂點後，得到了一個更小的 1577 個頂點的圖。這項工作將這些圖稱為 Mixon 圖，如上所示。
更小的色數為 5 的單位距離圖，這裡稱為 Heule 圖和 Parts 圖，是由 Marijn Heule 和 Jaan Parts 在 2018 年至 2020 年間從 de Grey 圖計算得出的。截至 2022 年，其中最小的是 509 個頂點的 Parts 圖 (Parts 2020)。
Mixon 圖在 Wolfram 語言中以如下方式實現：GraphData["MixonGraph1577"] 等。
另請參閱
de Grey 圖,
Golomb 圖,
哈德維格-納爾遜問題,
Heule 圖,
Moser 紡錘,
Parts 圖,
單位距離圖
使用 探索
參考文獻
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.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. "The Chromatic Number of the Plane Is at Least 5."Apr. 10, 2018. https://dustingmixon.wordpress.com/2018/04/10/the-chromatic-number-of-the-plane-is-at-least-5/.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.
請引用為
Weisstein, Eric W. “Mixon 圖。” 來自 —— 資源。 https://mathworld.tw/MixonGraphs.html
主題分類
