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

完全グラフばかり考えていたのですが、マイナーを考えないと本質にたどりつけなさそうなので考えています。Kn を彩色数を変えずにKmだけ分離していく(強連結を置換していく)には、完全2部グラフが必要になる。(片方はmだけど、もう片方が、m+1かn-1か、それ…