de Grey 图

De Grey (2018) 发现了色数为 5 的 单位距离图 的首批示例，从而证明了 Hadwiger-Nelson 问题（即平面的色数）的解至少为 5。虽然 de Grey 的原始图包含 个顶点，但他能够将这个数字（在修正后）减少到上面所示的 1581 个顶点的图（de Grey 2018），在本工作中称为 de Grey 图。

在最初的预印本发布几天后，Mixon (2018) 构建了一个类似的 1585 个顶点的图，从中移除 8 个顶点后，得到了一个更小的 1577 个顶点的图。这项工作将这两个图称为 Mixon 图。

更小的色数为 5 的 单位距离图，此处称为 Heule 图 和 Parts 图，是由 Marijn Heule 和 Jaan Parts 在 2018 年至 2020 年间通过计算从 de Grey 图中推导出来的。截至 2022 年，其中最小的是 509 个顶点的 Parts 图 (Parts 2020a)。

de Grey 图在 Wolfram 语言 中实现为GraphData["DeGreyGraph"].

由于 de Grey 的其他图是色数为 6 的 59 顶点和 60 顶点图，它们在 3 维（但不在 2 维）中是单位距离图，以及 Parts (2020b) 讨论的 126 顶点图。