組合せとグラフの理論（塩田）第11回 (1)　点彩色・彩色数の定義
戻る / 次へ

点彩色の定義

　まずは定義から。
Def.1　$G$ をループを持たない無向グラフとする。 $G$ の頂点に色を割り当て、隣接する頂点同士は別の色になるようにすることを「$G$ の点彩色」という。
Ex.2　次のグラフに点彩色を施してみましょう。 ( 今は色を塗りますが、実際に色を塗るのは大変なので、次からは単に色の番号を振って表します。)
　全ての頂点に異なる色を使えば当然点彩色になります。
　もっと少ない色で点彩色してみましょう。 隣接していなければ同じ色を塗ってもよいので
  とか  
でもOKです。

彩色数の定義

　色をたくさん使えば色は塗り易くなります。 しかし色が多いほどコストは増えます（インクをたくさん買わなければならない、とか）。 そこで、なるべく使う色を少なくしよう、というのが次の定義です。
Def.3　
  1. $G$ が $k$ 色で点彩色できるとき「 $G$ は $k$-彩色可能である」という。
  2. $G$ が点彩色できる 最少の色数 を「 $G$ の彩色数」と呼び、$\chi(G)$ と表す。
彩色数の示し方　$\chi(G)=k$ であることを示すには
  1. $G$ を点彩色するには $k$ 色以上必要であることを示し、かつ
  2. $G$ が本当に $k$ 色で点彩色できることを示す。
　1° は、$G$ が $k-1$ 色以下では点彩色できないことを示すことと同じです。

※　必要最小限と言わないといけないので 1° を忘れてはいけません。 こことても大事！！ （毎年口を酸っぱくして教えているのですが ... ）
Ex.4　$\chi(C_5)=3$.
  1. 2 色で点彩色しようとすると互い違いに色を使うしかなく、5 つ目の頂点にはどちらの色も使えなくなります。
  2. 次のように塗れば 3 色で点彩色できます。

戻る / 次へ