最小顶点着色

一个顶点着色是将标签或颜色分配给图的每个顶点，使得没有边连接两个颜色相同的顶点。最小化给定图所需颜色数量的顶点着色被称为的最小顶点着色。颜色的最小数量本身被称为色数，记为，色数为的图被称为 k-色图。

Brelaz 的启发式算法可以用来找到一个好的，但不一定是最小的顶点着色。找到最小着色可以使用暴力搜索（Christofides 1971; Wilf 1984; Skiena 1990, p. 214），尽管更复杂的方法可以显著更快。

使用启发式方法计算图的最小顶点着色在 Wolfram 语言中实现为FindVertexColoring[g].

Mehrotra 和 Trick (1996) 设计了一种列生成算法，用于计算色数和顶点着色，该算法可以快速解决大多数中小型图。

另请参阅

Brelaz 的启发式算法, Brooks 定理, 色数, 色多项式, 着色, 边色数, 边着色, 四色定理, 图着色, k-色图, k-可着色图, 标记图, 最小边着色, 顶点着色

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Christofides, N. “图的色数算法。” Computer J. 14, 38-39, 1971.Gould, R. (Ed.). 图论。 Menlo Park, CA: Benjamin-Cummings, 1988.Manvel, B. “极其贪婪的着色算法。” 在 图与应用 (Ed. F. Harary 和 J. Maybee). New York: Wiley, pp. 257-270, 1985.Matula D. W.; Marble, G.; and Isaacson, J. D. “图着色算法。” 在 图论与计算 (Ed. R. Read). New York: Academic Press, pp. 109-122, 1972.Mehrotra, A. 和 Trick, M. A. “图着色的列生成方法。” INFORMS J. on Computing 8, 344-354, 1996.Pemmaraju, S. 和 Skiena, S. 计算离散数学：Mathematica 中的组合数学和图论。 Cambridge, England: Cambridge University Press, 2003.Skiena, S. “寻找顶点着色。” §5.5.3 in 实现离散数学：Mathematica 中的组合数学和图论。 Reading, MA: Addison-Wesley, pp. 214-215, 1990.Soifer, A. 新数学着色书：着色数学及其创造者的多彩生活。 New York: Springer, 2024.Thomassen, C. “固定表面上图的

-着色的数量。” Disc. Math. 306, 3145-3153, 2006.Wilf, H. “回溯：图着色问题的

预期时间算法。” Info. Proc. Let. 18, 119-121, 1984.

请引用为

Weisstein, Eric W. “最小顶点着色。” 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/MinimumVertexColoring.html