西安电子科技大学$6.6.1图着色的基本概念软件学院教家教家用韦尔奇·鲍威尔法可以用最少的颜色数对任意图G进行正常着色，该方法的步骤如下：（1）将图G中的结点按度数递减的次序进行排列；（如果有相同度数的结点，这种排列是不唯一的。）（2）用一种与已着色结点所着颜色不同的新的颜色C对排列最靠前的尚未着色的结点着色，并按排列次序，对与前面已着上颜色C的结点不邻接的每一结点着同样的颜色C；（3）反复重复步骤（2），直到所有结点全部着上颜色为止。#整个过程所用的颜色数即为该图的色数。西安电子科技大学 §6.6.1 图着色的基本概念 软件学院