ヒューリスティックな彩色

k-degenerationグラフの順序で彩色してやれば、最大出次数+1以下で彩色できるのだけど、1点を除いて、最小最大出次数が2以上減る場合は彩色数が減るなと思った。

あと平面グラフで彩色数がk(≧4)のときに、頂点を追加して、色がkの頂点とその隣接点全部に接続したグラフを作って、それを彩色してやるとkになって間違っていることがわかるとかないかなとかおもった。