一般而言，即使是对于贪梦着色，这个上界△+1仍然是很大.事实上，用上面 的算法对顶点，着色时，我们只需要dG1…,()+1种颜色，而不是dG()+1 种颜色，就可以进行下去.注意到，这个时候，对于方>，算法忽略了的邻点 u,因此对于大多数图而言，有着很大的空间去改进△+1这个上界，这可以通过 选择一个特别有利的顶点顺序来开始着色：先选择那些顶点度比较大的顶点（这 时大部分邻点被忽略)，最后选择那些顶点度比较小的顶点.局部来看，如果是 Gu,·,中度数最小的顶点，则我们需要的dG,()+1种颜色也是最少 的，这可以容易地实现，只需要首先选取具有d(u)=(G)的顶点m,然后再取图 G一vm中度数最小的顶点作为-1，依次进行下去. 找个最小的k使得图G有这样一个顶点序列，使得它的每个顶点只有少于 个邻点排在它前面，这个k就叫做G的着色数(colouring number),记为col(G).我 们上面刚刚讨论的序列表明col(G)≤maXHCG6(H)+1.但是对于HCG,因为在 H的任意序列中，最后的那个顶点的“向后度数”就是它在H中的原来度数，它至 少为(H),所以显然有col(G)≥col(H)和col(0≥(H)+1.因此我们证明了下 面的结论 命题5.2.2 每个图G满足 X(G)≤col(G)=max{δ(H|HcG+1