読者です 読者をやめる 読者になる 読者になる

ハドワイガー予想って

lealgorithm.blogspot.jp

 K_{t+1} をマイナーとして含まないグラフは t-彩色可能 なのでしょうか?

もしかして対偶とって、t彩色可能でなければ、少なくとも K_{t+1}のマイナーを含むにすればよい?

だとするとそれに含まれる臨界グラフの頂点は全て次数t以上で、頂点数はt+1以上となるから、頂点がt+1となるまで縮約するとすれば、必ず K_{t+1}となるしかたがあるかな? なりそうな気はする。

つか、細分だけ考えれば、出次数の話だけだわ。
あとは縮約か。