組合せとグラフの理論(塩田)第11回 (6) 平面的グラフの場合

平面的グラフの場合

Lemma 14 $G$ が平面的グラフであれば、$G$ のいくつかの辺を縮約したグラフ $G'$ も平面的である。
証明 縮約とは辺を 1 点に潰すことなので、$G$ を平面グラフとして描画しておけば $G'$ にも辺の交差はありません。 (クラトフスキーの定理を使ってもわかります。)(証明終)
Th.15 $G$ が平面的グラフならば $\chi(G) \leqq 5$.
証明 これも Th.12 と同様に頂点数についての帰納法で示します。
 まず 第9回 Cor.19 により、$G$ は次数 $5$ 以下の頂点 $v$ を持ちます。
  1. $\rho(v) \leqq 4$ のとき
    Th.12 と同様に、$G-v$ を $5$ 色以下で点彩色しておけば $v$ に塗れる色が残っています。
  2. $\rho(v) = 5$ のとき
    $G$ は平面的なので $K_5$ は含みません。 従って $v$ の 5 つの隣接点 $v_1$, $\cdots$, $v_5$ のうち $v_1$ と $v_2$ は隣接しないと仮定できます。 $G$ を $vv_1$, $vv_2$ の 2 辺で縮約したグラフを $G'$ としましょう。 L'a 14 より $G'$ は平面的ゆえ、 帰納法の仮定より 5 色以下で点彩色できます。 そこで $G$ の $v$ 以外の頂点に $G'$ で塗った色を割り当てると、 $v_1$ と $v_2$ は隣接しないのでここまでは点彩色の条件を満たしており、 $v_1$, $\cdots$, $v_5$ には 4 色以下しか使っていませんので $v$ に塗れる色も残っています。(証明終)

    正二十面体グラフでは次のようになります。(本当に色を塗ってみました。)
     →   → 
    $G$ $G' =G\backslash \{vv_1,vv_2\}$
    を 5 色で点彩色しておく
    $v$ には紫が塗れる
 平面性がかなり強い条件なので、彩色数も低く抑えてられいる、ということです。