Hadwiger予想
Hadwiger予想近づいた気がしてきた。
その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想(en)がある。これは、彩色数 k のグラフはマイナーとして頂点 k 個の完全グラフを含む、という予想である。
平面グラフの彩色においては任意の面が3彩色可能なときとしたけど、平面じゃなければ、接続可能な点は頂点数分あるから、そうなりそう。
彩色数nのグラフGnに対し、頂点を1つ追加してGn+1にするには、Knグラフマイナーのn色にn本辺を引くのが、手順になるよな。
追記:
グラフを特徴づけるHadwiger予想と今回の面の彩色数の関係が理解できてきた気がした。
K3のグラフマイナーが面に相当し、これを頂点として4彩色のグラフを構成しているのが平面グラフだ。たぶん。
グラフ全体に処理を施していくことで面がつくれる。
縮退数kのグラフがのマイナーを持ってないかなー
