6-1 グラフ彩色

proper coloring $c$ があれば、各色 $i$ の色類
$$ V_i=\{v\in V(G)\mid c(v)=i\} $$
を取ります。同じ色の二頂点が隣接するとproperでないため、各 $V_i$ は独立集合です。色類は互いに交わらず全頂点を尽くします。
逆に独立集合への分割 $V(G)=V_1\sqcup\cdots\sqcup V_k$ があれば、$V_i$ の頂点へ色 $i$ を割り当てます。同じ色の頂点間には辺がないのでproper coloringです。□

clique内の任意の二頂点は隣接するので、proper coloringでは全頂点が相異なる色をもたなければなりません。最大cliqueに $\omega(G)$ 頂点あるため、少なくともその数の色が必要です。□

$v_i$ を彩色する時点で色が決まっているのは前に現れた頂点だけです。そのうち $v_i$ と隣接するものは高々 $d$ 個なので、禁止される色も高々 $d$ 色です。
$1,2,\ldots,d+1$ の $d+1$ 色のうち少なくとも一色は使われていません。その色を $v_i$ へ割り当てられます。こうして全頂点を処理できます。
各辺 $v_iv_j$ で $i< j$ とすると、$v_j$ を塗る際に $v_i$ の色を避けるため、最終的に両端の色は異なります。従ってproper coloringです。□

任意の頂点順序で、各頂点より前に現れる隣接頂点数はその次数以下、従って $\Delta(G)$ 以下です。greedy定理で $\Delta(G)+1$ 色あれば足ります。□

$(1)\Rightarrow(2)$。二部表示 $(X,Y)$ に対し、$X$ を色1、$Y$ を色2で塗ります。すべての辺は二部の間を結ぶのでproperです。
$(2)\Rightarrow(1)$。色1の頂点集合を $X$、色2を $Y$ とすれば、proper性により同色頂点間に辺はなく、すべての辺が二部の間を結びます。
$(1)\Leftrightarrow(3)$ は「二部グラフとマッチング」のodd cycle判定で完全に証明しました。
辺が一つ以上あれば隣接二頂点は異なる色を必要とするため $\chi(G)\ge2$。二部性から $\chi(G)\le2$ なので等号です。□

$K_n$ は全頂点がcliqueなので少なくとも $n$ 色必要で、各頂点へ別の色を与えれば $n$ 色で足ります。
$P_n$ は辺をもち、木なので二部グラフです。従って彩色数は2です。
$C_n$ は $n$ が偶数なら二部グラフなので2色です。$n$ が奇数ならodd cycleそのものなので2-colorableでなく、少なくとも3色必要です。一方、path $v_1,\ldots,v_{n-1}$ を色1,2で交互に塗り、最後の頂点 $v_n$ だけ色3にすればproperなので3色で足ります。□

頂点数 $n=|V(G)|$ に関する帰納法で示します。$n\le6$ なら各頂点へ異なる色を与えればよいです。
$n\ge7$ とし、より少ない頂点をもつすべてのsimple planar graphが6-colorableだと仮定します。「平面グラフ」の低次数頂点の定理から、$G$ には次数5以下の頂点 $v$ があります。
$G-v$ は頂点を一つ削ったplanar graphなので、帰納法の仮定により6色でproperに塗れます。$v$ の隣接頂点は高々5個であり、それらが使う色は高々5色です。六色のうち少なくとも一色は隣接頂点に使われていません。その色を $v$ へ割り当てれば、$G$ 全体のproper 6-coloringになります。□

$G$ の各色類は独立集合です。同じ色類の相異なる二頂点は $G$ で隣接しないため、$\overline G$ では隣接します。従って各色類は $\overline G$ のcliqueです。
逆に $V(G)$ が $\overline G$ の $k$ 個のcliqueへ分割されていれば、各clique内の二頂点は $G$ では隣接しません。各部分へ一色を割り当てると $G$ のproper coloringになります。□

外周長 $n-1$ が偶数、すなわち $n$ が奇数なら、外周は2色で塗れます。中心は外周の両色を避ける第四色ではなく第三色を使えばよいので $\chi(W_n)\le3$。中心と外周の隣接二頂点は三角形を作るため $\chi(W_n)\ge3$。従って3です。
外周長 $n-1$ が奇数、すなわち $n$ が偶数なら、外周には3色必要です。中心は外周の全頂点に隣接し、properなodd cycle彩色では三色すべてが外周に現れるため第四色が必要です。第四色を中心へ使えば足りるので $\chi(W_n)=4$。従って
$$ \chi(W_n)= \begin{cases} 3&n\text{ が奇数},\\ 4&n\text{ が偶数}. \end{cases} $$
□

最初の順序では
$$ c(x_1),c(x_2),c(x_3),c(x_4)=1,2,1,2 $$
となり二色です。
第二の順序では $x_1,x_4$ は色1、$x_2$ は $x_1$ を避け色2です。最後の $x_3$ は $x_4$ の色1と $x_2$ の色2を避け、色3になります。
$P_4$ は辺をもつ木、従って二部グラフなので真の彩色数は2です。第二のgreedy結果3は最適ではありません。□

proper coloringの各色類は独立集合なので、一色類に含まれる頂点は高々 $\alpha(G)$ 個です。$k$ 色で全 $n$ 頂点を塗れたなら
$$ n\le k\alpha(G). $$
従って
$$ k\ge\frac{n}{\alpha(G)}. $$
$k$ は整数なので $k\ge\lceil n/\alpha(G)\rceil$。最小の $k=\chi(G)$ にも同じ下界が成り立ちます。□

planar辺数上界 $e\le3v-6$ と握手補題から
$$ \frac1v\sum_{x\in V}\deg(x) =\frac{2e}{v} \le\frac{2(3v-6)}v =6-\frac{12}{v}<6. $$
すべての頂点の次数が6以上なら平均も6以上になるため矛盾です。従って次数5以下の頂点があります。□

$A,B,C$ が三角形を作るので少なくとも3色必要です。また $D,E,F$ も三角形です。
次の3-coloringを取れます。
$$ c(A)=1,\quad c(B)=2,\quad c(C)=3, $$
辺 $CD$ があるので $D$ を1とし、
$$ c(D)=1,\quad c(E)=2,\quad c(F)=3 $$
とします。列挙された各辺の両端は異なる色です。従って $\chi=3$ で、色1,2,3を三つの時間帯とすればよいです。□