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

グラフ理論について、今のところわかったこと

任意のグラフをGとし、その彩色数を \chi(G) = kとあらわす。 1点uを加えG'とするとき、その接続数がk未満の場合には必ず \chi(G') = kが成立する。

証明
 \chi(G) = kであるGからk未満の点を選択するとき、uはかならずk色の中から彩色の色を選択できる。 よって上記が成りたつ。
(証明終わり)

任意のグラフをGとし、その彩色数を \chi(G) = kとあらわす。 1点uを加えG'とするとき、その頂点が全点に接続する場合には必ず \chi(G') = k+1が成立する。

証明
 \chi(G) = kであるGに頂点uを加え、全点に接続するならば、uは必ず全色に接続し、k+1色目が必要になる。
もし \chi(G') \le kであるなら、彩色数が彩色できる最小の色数という前提に反する。
また \chi(G') = k+1で十分であり、 \chi(G') \gt k+1にはならない。

(証明終わり)


上記より

  • 頂点数v, 彩色数kをあたえられたとき、接続数をk未満とする頂点を追加する操作を繰り返すことで、頂点数vで彩色数k以下を満たすグラフを作ることができる。
    • vがkに対し、十分大きい時、頂点数v,彩色数kのグラフを作成できる。
  • 無向グラフの頂点を適当に順序付けして、その任意の2頂点i,j (i < j)に辺があるとき、jからiに対し向きをつける。全ての頂点に対し、この出力辺をk本以内にできるとき、k+1彩色可能。ただし彩色数(Chromatic number)と一致するとは限らない。
  • 上記からn正則グラフはn+1彩色可能、ただし彩色数(Chromatic number)と一致するとは限らない。
    • ピーターセングラフがわかりやすい例

多分これは正則グラフではBrooksの定理と一致して、一般のグラフでは上限をよく押さえつけるものになるかな。
Brooks' theorem - Wikipedia

kousuke.hatenablog.com


完全2部グラフKi,jを彩色した色クラスをそれぞれ閉路にしたとき(i,j >= 2)

  • その彩色数は4(i,jが共に偶数),5(i,jが偶数、奇数),6(i,j共に奇数)になる。

偶閉路が2彩色、奇閉路が3彩色できることによる。



完全2部グラフKi,jを彩色した色クラスを完全グラフにしたとき

  • その彩色数はi+jになる。

Ki+jと同一なことによる。


奇閉路に一点加えて彩色数を4とするためには全点に接続しないといけない。



俺の中でP=NPの機運が高まっている。