顶点着色是将标签或颜色分配给图的每个顶点，使得没有边连接两个颜色相同的顶点。最常见的顶点着色类型是寻求最小化给定图的颜色数量。这种着色被称为最小顶点着色，图 
的顶点可以着色的最小颜色数称为色数，记为 
。
使用 
种或更少颜色的图的顶点着色被称为 k-着色。具有 
-着色（因此色数 
）的图被称为 k-可着色图，而具有色数 
的图称为 k-色图。唯一的可单色（因此是单色的）图是空图，而双色图恰好是二分图。四色定理确定所有平面图都是 4-可着色的。
顶点着色
另请参阅
Brelaz 启发式算法, Brooks 定理, 色数, 色多项式, 着色, 边色数, 边着色, 四色定理, 图着色, k-色图, k-可着色图, k-着色, 标记图, 最小边着色, 最小顶点着色使用 Wolfram|Alpha 探索
参考文献
Christofides, N. "An Algorithm for the Chromatic Number of a Graph." Computer J. 14, 38-39, 1971.Gould, R. (Ed.). Graph Theory. Menlo Park, CA: Benjamin-Cummings, 1988.Manvel, B. "Extremely Greedy Coloring Algorithms." In Graphs and Applications (Ed. F. Harary and J. Maybee). New York: Wiley, pp. 257-270, 1985.Matula D. W.; Marble, G.; and Isaacson, J. D. "Graph Coloring Algorithms." In Graph Theory and Computing (Ed. R. Read). New York: Academic Press, pp. 109-122, 1972.Skiena, S. "Finding a Vertex Coloring." §5.5.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 214-215, 1990.Thomassen, C. "The Number of
-Colorings of a Graph on a Fixed Surface." Disc. Math. 306, 3145-3153, 2006.Wilf, H. "Backtrack: An 
Expected Time Algorithm for the Graph Coloring Problem." Info. Proc. Let. 18, 119-121, 1984.在 Wolfram|Alpha 中被引用
顶点着色引用为
Weisstein, Eric W. "顶点着色。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/VertexColoring.html