上述图着色算法是最简单明了的算法描述，实际上是基于冲突图的结群，使用贪婪算法进行结群，其着色效果不一定最优（颜色最少）。下面给出一个改进方案。
　　冲突图G由二元式组成：
　　　　　　G = { V, E }
　　其中　　V = { v_i | 需要被着一种颜色的区域i}
　　　　　　E = { (v_i , v_j)| 区域i与区域j相邻，不可着一种颜色，二者冲突}
　　设结群后的结果用C表示。
　　　　　　C = { S₁, S₂, S_i , S_n }
　　　　　　S_i是无冲突集（见定义4）
　　　　　　S_i ∩ S_j =　( S_i , S_j ∈ C )
　　　　　　V C

　　定义1：完全冲突集M是V的一个子集，M中的任意2个结点皆相互冲突。
　　定义2：完全冲突集M中结点个数减1称作M的冲突度，记作d_m。
　　定义3：MM = {∪M_k | M_k是G的完全冲突集 }。
　　定义4：无冲突集S是V的一个子集，S中的任意2个结点皆不冲突。
　　推论1： 从完全冲突集M中删去任意一个结点后的剩余部分N仍然是一个完全冲突集。并且d_n = d_m - 1
　　推论2： 冲突度 d_m= 0的完全冲突集M是完全冲突集的一个特殊情况，即M中只有1个元素m，结点m和V中任何其他结点都不冲突。

　　Step1 初始化： 令C = ;
　　Step2 准备工作： 为冲突图G建立MM；
　　Step3 从MM中选取一个冲突度最大的元素M_k，对M_k中每一个元素执行以下操作：
　　若结点 m (M_k ∩ V)，则
　　　(1) C = C ∪ m；
　　　(2) 修改M_k及其冲突度： M_k = M_k - m； d_m = d_m - 1；
　　　(3) 修改V： V = V - m；
　　Step5 以冲突度为优先级对MM中的元素排序，以冲突度递降的顺序逐一分析MM中每一个元素M_k，对M_k中每一个元素m执行以下操作：
　　若{ S_i ∪ m }是无冲突集，则
　　　(1)S_i = S_i ∪ m；
　　　(2)修改M_k及其冲突度： M_k = M_k - m； d_m = d_m - 1；
　　　(3)修改V： V = V - m；
　　Step6 若V = 　算法结束；否则转Step3。