>この違いによって、1回の処理でグラフから一定割合の頂点を減らせるようになります。例えば、毎回数個だけ減らす場合はグラフが空に
>なるまで大量の繰り返しが必要ですが、毎回一定割合ずつ減らせるなら、1000個、500個、250個というように急速に問題を小さくできます。

8202種類のパターンの最大サイズは有限だから、それより遥かに大きなグラフでは「毎回一定割合ずつ減らせる」なんてことは有り得ない
わけで、この主張は間違い

>その結果、4色で塗り分けるための計算量は従来のO(n2)からO(nlog_n)へと改善されました。

最大サイズがmとして、頂点数n=m^kのグラフの頂点数をm^(k-1)にする手間はn^2/m程度、つまりO(n^2)だから、改善になってねーじゃん