頂點著色是將標籤或顏色分配給圖的每個頂點，使得沒有邊連線兩個顏色相同的頂點。最常見的頂點著色型別是尋求最小化給定圖的顏色數量。這種著色被稱為最小頂點著色，圖 
的頂點可以著色的最小顏色數稱為色數，記為 
。
使用 
種或更少顏色的圖的頂點著色被稱為 k-著色。具有 
-著色（因此色數 
）的圖被稱為 k-可著色圖，而具有色數 
的圖稱為 k-色圖。唯一的可單色（因此是單色的）圖是空圖，而雙色圖恰好是二分圖。四色定理確定所有平面圖都是 4-可著色的。
頂點著色
另請參閱
Brelaz 啟發式演算法, Brooks 定理, 色數, 色多項式, 著色, 邊色數, 邊著色, 四色定理, 圖著色, k-色圖, k-可著色圖, k-著色, 標記圖, 最小邊著色, 最小頂點著色使用 探索
參考文獻
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.在 中被引用
頂點著色引用為
Weisstein, Eric W. "頂點著色。" 來自 —— 資源。 https://mathworld.tw/VertexColoring.html