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

任意のグラフを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)