彩色数、グラフマイナーとは

イメージ的には電子部品のようなもので3次以上の完全グラフをマイナーとして持つネットワークが内部回路、内部回路も同様に入れ子にできる。その内部ネットワークを十分に機能させるために彩色数分のソケットが必要。

色を示す頂点を用意し、一つの部品のソケットには色の重複がないように割り当てるように、全てのソケットと繋ぐときの最小頂点数をみつけるのが彩色問題。

追記:
まとめるとグラフGの彩色数をP(G)とするとGを二つのグラフGa,Gbに分割したとき、P(G) = max(P(Ga), P(Gb))P(G) ≧ max(P(Ga), P(Gb))にたぶんなる(これはそんな定理もあった気がする)。
P(G) > max(P(Ga), P(Gb))の時は多分、P(G)=nとすると彩色数を決めるKnのグラフマイナーをぶった切ってる。

Ga, Gbはさらに分割可能なので、上記の式を帰納法で解いた結果はHadwiger予想とおそらく同じ。
min側の意味もGa,Gbの連結度的なものになりそう。

彩色組み合わせの数もKnから任意の辺に頂点を追加する操作を行う操作回数をoとすると彩色組み合わせはP(Kn)*(P(G)-2)^oになる筈だし、マイナーに閉じた操作での彩色組み合わせの数の変化はおそらく示せそう。