给定一个图，我们怎样来决定它的色数呢？怎样才能找到一个使用尽可能少颜 色的顶点着色呢？色数与图的其他不变量（例如平均度、连通度或者围长）的关系 是怎样的呢？ 从色数的定义，我们可以直接得到下面这个上界 命题5.2.1每个具有m条边的图满足 1 xg≤2+V2m+4 证明设c是图G中一个具有k=X(G)种颜色的顶点着色，那么在G的每 两个色类之间都至少存在一条边，否则，我们可以把这两个色类着同一种颜色.因 此m≥。k(化-1).从这个不等式中解出k,就得到了我们想要的结论. 0