图着色（图染色）：在图论中，把“颜色”分配给图的顶点（最常见）或边，使得相邻顶点（或相邻边）不出现同色；通常目标是用尽可能少的颜色完成分配。所需最少颜色数称为色数（chromatic number）。
/ˈɡræf ˈkʌlərɪŋ/
Graph coloring helps schedule exams so that no student has two exams at the same time.
图着色可以用来安排考试时间表，确保没有学生在同一时间参加两门考试。
Finding the minimum number of colors needed for a general graph coloring problem is computationally difficult.
为一般图的图着色问题找到所需最少颜色数在计算上非常困难。
graph 源自希腊语 *graph-*（“书写、描画”），在数学中引申为由点和线构成的“图”；coloring 来自 color（“颜色”），在图论里借用“上色”这一直观比喻，表示给顶点/边分配类别或标签，以满足“不冲突”的约束。该术语在20世纪图论与组合数学发展中逐渐固定下来。
Select Language