グラフ彩色エクスプローラー

ピーターセングラフは 10 個の頂点、15 個の辺を持ち、三角形を含まない。したがってパネルは χ ≥ 2 と表示する。真の染色数を求めよ。これはピーターセングラフの状態である。

1. どのようなグラフからも 2 つの界が自明に得られる。すなわち、最大クリックの大きさ以上の色数が必要であることと、最大次数に 1 を加えた値を超える色数は決して必要としないことである。

   $$\omega (G)\le \chi (G)\le \Delta (G)+1:\text{Petersen has }\omega =2,\Delta =3⟹2\le \chi \le 4$$

2. ピーターセングラフの内周は 5 であるため、内部に三角形は一切存在せず、クリック数による下限は自明な 2 に潰れてしまう。それがパネルの報告する数値である。

   $$\text{girth}=5⟹\text{no triangle}⟹\omega =2,\text{yet the graph is not bipartite}$$

3. 2 色での彩色が可能なのはグラフが 2 部グラフである場合のみであり、2 部グラフであるとは奇サイクルが存在しないことを意味する。外側の五角形は 5 サイクルであるため、2 色での彩色は不可能である。

   $$\text{bipartite}⟺\text{no odd cycle};\text{the outer 5-cycle is odd}⟹\chi \ge 3$$

4. 三色で塗り分けられる。実際の塗り分けを一つ示せば、上界の証明として十分である。外側の五角形を一周する順に 1、2、1、2、3 と塗り、同じ順で五つの内側の頂点を 2、1、3、3、2 と塗る。それぞれ、同じスポーク上の外側の頂点と対応している。十五本すべての辺をたどると、どの辺でも両端の色は異なる。

   $$\text{a 3-colouring exists}⟹\chi =3,\text{strictly above the clique bound }\omega =2$$

5. ブルックスの定理は上限側から同じことを示している。完全グラフでも奇サイクルでもない連結グラフが必要とする色数は高々 Δ 色であり、ここでは Δ は 3 である。

   $$|V|=10,|E|=15,\Delta =3:\text{Brooks’ theorem gives }\chi \le 3\text{for a connected non-complete graph}$$

次は K₄ — 4 個の頂点と、全 6 本の辺が存在する。χ を求め、各界をピーターセングラフでの結果と比較せよ。これは完全グラフ K4の状態である。

1. 図を過信するのではなく辺を数えよ。4 個の頂点のすべてのペアが結ばれており、ペアは 6 つ存在する。

   $$K_4:|V|=4,|E|=\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6,\text{every pair adjacent}$$

2. すべての頂点が他のすべての頂点と隣接しているため、どの 2 つの頂点も同じ色を共有することはできない。これは 4 という下限を与え、定義以上の議論を必要としない。

   $$\text{all four vertices are mutually adjacent}⟹\omega =4⟹\chi \ge 4$$

3. 4 色で十分であることは明白であるため、下限は満たされる。同様の推論により、すべての n について χ(Kₙ) = n が導かれ、これが完全グラフを扱いやすいケースにしている。

   $$\text{four colours suffice trivially}⟹\chi (K_n)=n$$

4. 2 つのグラフを並べて比較してみよ。同じ問い、同じ 2 つの界であり、それらの間のギャップこそがこの主題のすべてである。

   $$\text{here }\omega =\chi =4:\text{the bound is tight, and Petersen showed it need not be}$$

5. ここでブルックスの定理がどのような位置づけにあるかに注目されたい。その Δ = 3 という上限は K₄ に対しては誤りとなるため、完全グラフが名指しで例外として除外されているのである。

   $$\Delta +1=4\text{as well — Brooks’ theorem excludes complete graphs for exactly this reason}$$