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

彩色問題

四色定理のことをたまに考えるんだけど、平面グラフにおいて、任意の1面に対し、その面を構成する閉路の頂点を3彩色し、且つ、グラフ全体を4彩色する塗り方があるってことに気付いた。

多分、正しい。

平面グラフGにより構成される面Fの内、任意の面fを構成する閉路をCfとする。
このCfを3彩色し、Gを4彩色する方法が必ず存在する。

Gに点uを加えて、G'を作るとき、uは必ずある面f内に配置される(グラフの外も面と考える)。
この時fを構成する閉路Cfが必ず4色必要とされる場合、uからCf上の4色の点に辺を作成したG'は必ず5色必要となり、四色定理に反する。

追記:

帰納法でもできそう。GにK4が含まれる場合には成立する。
たぶんGには、K4グラフマイナーが含まれる場合に成立する。かな? グラフマイナーよくわかってない。
そしてK4グラフマイナーを含まない場合に、CfおよびGが3彩色可能になりそう。なのかな? まだわからない。

帰納法でできれば四色問題の別証明になるのかなぁ?

追記2:

Gnが3彩色できる場合、3色の閉路で2色の頂点のみに接続する場合か、2色の閉路内に1頂点を加えた場合なので、3彩色のグラフの列挙とか、判定式もできそう。。