色数,数学上在图论中一个图的最小着色数。
顶点着色及色数
顶点着色：设图，我们使用n种颜色对V中的每个顶点进行着色，如果满足没有相邻顶点着相同颜色， 则称其为G的一个n-顶点着色，n-顶点着色常简称为n-着色。
k-可着色：对于图G，如果存在一个G的k-顶点着色，则我们称图G为k-可着色。
色数：对于整数k，如果G为k-可着色，且不存在正数k’，且满足G为k'-可着色，则我们称k为G的色数（最小着色数），通常用来表示。
如图1，是对Petersen图的一种着色。观察可发现，所有相邻顶点均为不同颜色，所以这是一个Petersen图的一个3-顶点着色，且Petersen图为3-可着色。注意，Petersen图的色数也是3，因为Petersen图不可2着色。
色数的性质
1- 对于, |G|=N,
证明：
G的顶点数为N，用N种颜色对其顶点着色使得每个顶点颜色均不相同，必然可以保证相邻顶点不同色。
当G的N个顶点全都不连通时，可全部用同一种颜色着色。所以，。
2- ，是完全图
证明：
充分性：如果G是
完全图，，即任意两顶点相邻，所以任意两个顶点必须着不同颜色，.
必要性：我们假设存在G，G不是完全图，且。由于G不是完全图，.我们设u的着色c(u)，v的着色为c(v)。由于u,v并不相邻，且u和v的颜色与其它顶点的颜色均不相同，我们可以令c(v)=c(u),即给v着u的颜色。这样依然可以保证相邻顶点不同色，所以，产生矛盾。所以如果，G必须是完全图。
3- G=，定义了图G中最大完全子图的大小，
证明：
由于完全图的色数等于它的顶点数，对于G中的完全
子图，至少需要其完全子图大小数量的颜色才能进行着色。所以。
证明：
由定义可知，,。采用种颜色，对于每个顶点v，我们都可以让它自己和所有邻居点全部采用不同的颜色。这样就可以产生一种正确的着色方式。
证明：
必要性：当G为二部图时，G可以分为两个部分和，且和内部的点无边相连。所以我们可以直接为和中的点分别赋予不同的颜色。
充分性：图中不存在长度为
奇数的圈。假设图中存在长度为奇数的圈,2种颜色一定无法着色。由于相邻点无法着相同的颜色，我们令,为两种不同的颜色。最终和也会是相同的颜色，但它们是相邻的点。所以如果图中存在长度为奇数的圈，。即图中不存在长度为奇数的圈为二部图。
6- ，G为
连通图且G既不是长度为奇数的圈也不是完全图，那么。
证明：
设|G|=n, 。由于G不是完全图，所以. 当k=2, G一定是一条路径或者是一个长度为偶数的圈，易知. 假设k。我们设,并且利用贪心算法分下列三种情况进行着色，证明.
情况1：假定G不是k-正则图，即不是所有点的度均为k。这样一定存在一个点u，。我们令这个点为,,表示的邻居点。同样地，对于任意i,
由于G有有限个点，所以最终会停止，图示见图2.
下面我们为这些集合中的点进行编号。中的点编号为,中的点编号为。一直这样知道所有的点都被成功编号。下面我们按照编号从到依次进行着色。对于任意一个（）,u必然有一个邻居点在中，所以编号在u之前的邻居点的个数至多只有k-1个，至多只会占用k-1种颜色，那么我们一定可以采用一种没有占用过的颜色对u进行着色。如果,由于u为我们找到的度小于k的点，所以它已着色的邻居点个数依然小于k，我们仍旧可以给u着色。按照这种模式，我们可以采用不超过k种颜色对所有点进行着色。
情况2：假设G是一个k-正则图并且G有一个割点v，如图3。由于v为G的割点，删去v必然造成G的不连通性。我们假设删去v后产生的连通分支为。图(i=1,2,...,t). 考虑图，v在中的度小于k，那么在中我们可以使用情况1中的方法进行采用不超过k种颜色进行着色。同理，在所有中均可以采用这种方法进行着色，我们可以假定在所有中v的颜色都相同（如果不相同，直接交换颜色即可）。最终，对于所有G中的点，我们都可以用不超过k种颜色进行成功着色。
情况3：假设G是一个k-正则图且G中没有
割点，所以G的割点集的大小大于等于2。
3.1 G的最小割点集的大小大于2，那么删去任意两个点，G依然是连通的。我们选取一个点u，为它的两个邻居点，且。我们一定可以找到这样的三个点，否则G就是一个完全图。我们还知道，是连通的。
3.2 G的最小割点集的大小为2。那么存在一对点v,w，是不连通的。我们设定G-{v,w}的连通分支为 。由于,任意至少含有两个点，v至少连通了中的一个点。我们假定且u是v的邻居点。如果u是图G-v的一个割点，那么中至少还存在一个点y，满足y不是G-v的割点，并且y与v相连。我们把这个与v相连且不是G-v割点的点记为。同理，在中，我们可以找到这样的点。
在这两种情况下，我们都可以找到点，满足且是连通的。接下来我们可以利用贪心算法对图进行着色。
首先将找到的点分别编号为。接下来我们找到一个的邻居点，该邻居点不是(这样的点必然可以找到，因为)，我们将这个点编号为。接下来再找一个或的未编号邻居点，编号为。我们一直重复这个过程，直到所有点都成功编号。由于是连通的，对于任意。
编号完成后，我们可以利用贪心算法按顺序从到开始编号。由于，我们可以给它们赋予同样的颜色。对于，它最多只有k-1个编号在前的邻居点，最多占用k-1种颜色，一定可以赋予一种新的颜色。对于，由于它有两个邻居点着同一种颜色，其k个邻居点也至多占用k-1种颜色，依然可以着色。所以，所有点都可以用k种颜色进行着色。
对于以上三种情况，均可以用k种颜色进行着色，所以。
6- 奇圈和奇阶轮图的色数均为3，而偶阶轮图的色数为4。
与独立集关系
独立集定义：图，，如果S中的任意两个顶点在G中均不邻接，则称S是一个独立集。
独立数：对于独立集S，如果不存在S’，使，S称为最大独立集。S种顶点的个数成为G的独立数，记为。
定理：设，S是G的独立集当且仅当是G的一个覆盖。
推论：对于p阶图G，有
色数与独立集：具有任何一种相同颜色的所有顶点的集是独立的，因为相同颜色的点必定不是邻接点。因此，图G的一个n-着色是把V(G)分成n个（可能有空的）独立集的一个划分
色数与独立数满足：, |V|=n,
证明：
由于G的一个n着色可以看作是将V(G)分成n给独立集的划分，设,我们可以将G分为k个独立集。根据独立集的定义，。所以.
由于k为G的一个最小划分，
所以.