着色图
图形着色不过是在某些约束下标记图形组件（例如顶点，边线和区域）的一种简单方法。在图形中，没有用最小数量的颜色对两个相邻的顶点，相邻的边或相邻的区域进行着色。此数字称为色数，而该图称为正确着色的图。
在对图形进行着色时，在图形上设置的约束条件包括颜色，着色顺序，颜色分配方式等。对顶点或特定区域进行着色。因此，具有相同颜色的顶点或区域形成独立的集合。
顶点着色
顶点着色是将颜色分配给图形“G”的顶点，以使两个相邻的顶点都不具有相同的颜色。简而言之，边的两个顶点都不应具有相同的颜色。
色数
图“G”的顶点着色所需的最少颜色数称为G的色数，用X(G)表示。
当且仅当“GX”为空图时，χ(G)=1。如果'GX'不是空图，则χ(G)≥2
示例
注-如果顶点着色最多使用n种颜色，即X(G)≤n，则认为图'G'是n可覆盖的。
区域着色
区域着色是将颜色分配给平面图的区域，这样就不会有两个相邻的区域具有相同的颜色。如果两个区域具有相同的边缘，则称它们是相邻的。
示例
看下图。区域“aeb”和“befc”是相邻的，因为在这两个区域之间存在一个公共边“be”。
类似地，其他区域也基于邻接而着色。该图的颜色如下-
示例
Kn的色数为
a）n
b）n–1
c）中⌊ñ/2⌋
d）⌈ñ/2⌉
考虑带有K4的示例。
在完整图中，每个顶点都与其余（n–1）个顶点相邻。因此，每个顶点都需要一种新的颜色。因此，Kn=n的色数。
图形着色的应用
图着色是图论中最重要的概念之一。它用于计算机科学的许多实时应用中，例如-
聚类
数据挖掘
影像撷取
图像分割
联网
资源分配
流程调度