彩色数判定へのアプローチ

最初は彩色数kのグラフは2部グラフマッチングか最大流にできるとおもっていたのですが、制限付きナップサック問題かなにかに帰着できそうな気がしています。
たしかに組み合わせ問題なのでナップサック問題になってもおかしくなさそうです。

現在、v,e,kのみの数値でのプロトタイプを作成しています、ピーターセングラフはちゃんと3とでますが、2部グラフKn,mが2で出ません。

ただしある程度法則性があってn = mのときnででますし、m = n+1のときmででます。m = n + 2のとき、(m + n) / 2ででていて、完全2部グラフは完全グラフ内に含まれる。というのが仮説としてでてきました。

3彩色問題はヒューリスティックな感じの判定プログラムはつくれそうな気がします。
ただ理論的裏付けがなく、それが判定式となるのかはまだまだ研究中です。