組合せとグラフの理論（塩田）2024年度

基本的命題

　基本的な性質を命題としてまとめていきましょう。

Prop.5　

$\chi(G)=1$ であることと、$G$ が空グラフであることは同値である。
$\chi(G)=2$ であることと、$G$ が空でない二部グラフであることは同値である。
$T$ が 2 頂点以上の木であれば $\chi(T)=2$ である。
$\chi(K_n) = n$.
$n \geqq 3$ に対して $\dps{\chi(C_n)=\left\{ \begin{array}{ll} 2 & n \mbox{ が偶数のとき} \\ 3 & n \mbox{ が奇数のとき.} \\ \end{array} \right.}$

証明　

$G$ が空グラフであれば隣接関係が全くないので $\chi(G)=1$ です。辺が 1 本でもあればその両端に違う色を使う必要があるので $\chi(G) \geqq 2$ になります。
$G$ は空でないので $\chi(G) \geqq 2$ であり、次のように 2 色で点彩色できます。
木は二部グラフゆえ。
完全グラフは全ての頂点が互いに隣接していますので、全ての頂点に違う色を使う必要があります。
Ex.4 のように、$n$ が偶数なら互い違いに塗ればよく、$n$ が奇数なら 3 色目が必要になります。

(証明終)

部分グラフとの関係

Prop.6　$H$ をグラフ $G$ の部分グラフとすると $\chi(H)$ $\chi(G)$.

... には $\leqq$ と $\geqq$ のどちらが入るでしょうか。

Prop.7　$G$ が部分グラフとして $K_n$ を含んでいれば $\chi(G) \geqq n$.

Ex.8　一筆書きでよく使うこのグラフは

$K_4$ を部分グラフとして含んでいますので彩色数は 4 以上で ( 1° )、実際に次のように 4 色で点彩色できます ( 2° )。

　この例のように Prop.7 は 彩色数の示し方の 1°　に役立つのですが、残念なことに逆が成り立ちません。

Rem.9　$\chi(G)=n$ であっても $G$ が $K_n$ を含むとは言えない。

　従って、$G$ の含む完全グラフを調べても $\chi(G)$ は決められません。 ここもとても大事！！

　次の節では Rem.9 のような $G$ を作って見せます。