Colorful Tree Game - 情報妖精の競プロ日記

はじめに

この記事は、木 Advent Calendar 2023 - Adventarの23日目です。

皆さんは彩色数はご存じですね？
グラフ $G$ の各頂点に対して、隣接する頂点とは異なる色になるように色を割り当てる時、必要な色数の最小値を彩色数 $\chi(G)$ と呼びます。

木 $T$ に対して、彩色数 $\chi(T) \leq 2$ が容易に示せますし、2頂点以上あれば明らかに $\chi(T) = 2$ です。
従って、木が与えられた時の彩色数は簡単に分かりますね。
では、ゲーム彩色数も簡単に分かるのでしょうか。

ゲーム彩色数とは？

まず、頂点彩色ゲームを以下のように定義します。

頂点彩色ゲーム

グラフ $G$ に対して、 $k-$ 頂点彩色ゲームを以下のように定義します。

はじめに、グラフ $G$ の各頂点に色 $0$ を割り当てる。
Aliceが先行で、全ての頂点に $0$ 以外の色が割り当てられるか、操作が不可能になるまでAliceとBobが交互に以下のプレイを行う。
ターンプレイヤーは $0$ が書かれた頂点を一つ選び、 $1$ 以上 $k$ 以下の整数のうち隣接する頂点に書かれていない数を一つ選んで上書きする。
全ての頂点に $0$ 以外の色が割り当てられればAliceの勝ち、操作が不可能になった(隣接する頂点が $1$ から $k$ まで全て書かれた頂点が存在した)らBobの勝ち。

ゲーム彩色数

上の頂点彩色ゲームは、 $k$ が大きいほどAliceが勝ちやすくなると考えられています。
グラフ $G$ に対して、ある整数 $c$ が存在して、 $k \lt c$ ならばBobが勝ち、 $k = c$ ならばAliceが勝つとき、値 $c$ を $G$ のゲーム彩色数と呼び、 $\chi_g(G)$ と表記します。

ゲーム彩色の性質

ゲーム彩色数は、本来の彩色数より大きくなることが期待されます。
まず、少なくとも $\chi(G) \leq \chi_g(G)$ が明らかです*1。
また、明らかに $\chi_g(G) \leq \Delta(G) + 1$ です*2。
ただ、彩色数がかなり小さいからと言って、ゲーム彩色数が小さくなるとは限りません。

例えば、二部グラフは定義より明らかに $\chi(G) = 2$ です。
しかし、二部グラフでありながらゲーム彩色数が無限に大きいグラフを構築することができます。

具体的な構築方法

二部グラフなので、頂点集合を $S, T$ の二つに分けて考えます。
$S$ は $k$ 頂点あり、順に $S_0, S_1, \ldots, S_{k-1}$ と番号が付いているものとします。
また、 $T$ は $2^k$ 頂点あり、順に $T_0, T_1, \ldots, T_{2^k-1}$ と番号が付いているものとします。
そして、 $S_i$ と $T_j$ は、2進法で $j$ の $i$ 桁目が1であるとき、かつその時に限り辺が張られているものとします。

$1$ ターン目から $k$ ターン目までのBobの戦略は以下のようになります。

現在のターンが $t$ ターン目の時、 $T$ 上の頂点であって隣接する頂点に色が塗られていないもののうち次数が最大のものを選び(これは一意に定まります)、その頂点を色 $t$ で塗る

この時、Aliceの行動に依らず $S$ 上で最後に塗られる頂点は色 $1, 2, \ldots, k-1$ が使えないことが示せるため、 $\chi_g(G) \geq k$ が示せます*3。

二部グラフではゲーム彩色数を抑えることができませんでしたが、ではもっと強いクラスではどうでしょうか？

実は、木においてはゲーム彩色数が有限で抑えられることが示せます。

木のゲーム彩色数

では、木における彩色数を考えていきましょう。
まずは、下限から見積もってみます。

定理1. $\chi_g(T) = 1$ である必要十分条件は、 $|V(T)| = 1$
証明1. 辺で隣接する二つの頂点は相異なる色で塗る必要があることと、1頂点の木は自明に $\chi_g(T)=1$ であることから明らか。

定理2. $\chi_g(T) = 2$ である必要十分条件は、木の直径が $1$ 以上 $2$ 以下であること
証明2. 直径が $0$ の時は明らかなので、まず直径が $1$ および $2$ の時について考える。
直径が $1$ のグラフは $P_2$ のみであり、この場合の答えは自明。
また、直径が $2$ のグラフは星のみであり、Aliceが最初に中心を選べば良い。
次に、直径が $3$ 以上のグラフを考えると、このグラフは $P_4$ を含む。
この時、 $P_4$ は、Aliceが $P_4$ 上の頂点を一つ塗った時、Bobはそこから距離 $2$ の頂点を異なる色で塗ることで必ず $3$ 色以上に持ち込める。
また、どの頂点 $v$ も $v$ を含む $P_4$ が存在することが示せるので、直径が $3$ 以上のグラフは $\chi_g(T) \geq 3$ が示された。

これで、まず $\chi_g(T) \leq 2$ の場合は分かりました。
ですが、3色以上になるとAliceの戦略もBobの戦略も多様になるため、ここから下限を上げるのは難しそうに思えます。
そこで、次は上界を見積もってみましょう。

定理3. $\chi_g(T) \leq 4$
証明3. Aliceの戦略について説明する。
まず、葉のみが彩色されていて良い木を幹 $R$ と書くことにする。
木に色を付けていったとき、その色によって木は幾つかの幹に分解できる。
分解を行うときは常に極大な幹を取ることにすると、このような分解方法は一意に定まる。
そこで、この幹についてのAliceの戦略を定めていく。

3個の葉が塗られている幹が存在する
この時、Aliceはその三つの頂点の中央を四色目で塗ることによって、二個の葉が塗られている幹 $3$ つに分解することができる。
3個の葉が塗られている幹は存在しないが、2個の葉が塗られている幹が存在する
この時、Aliceはその二つの頂点の中央を三色目で塗ることによって、二個の葉が塗られている幹 $2$ つに分解することができる。
全ての幹は1個以下の葉しか塗られていない
この時、Aliceがどの頂点を選んでも全ての幹は2個以下の葉で塗られることになるので、どれでも好きに選んでよい。

この戦略を選ぶとき、どのようにBobが頂点を選んでもAliceのターンには高々1個しか3個の葉が塗られている幹は存在しないことから、 $\chi_g(T) \leq 4$ を示すことができる。

以上より、高々定数個を除いて全ての木のゲーム彩色数は $3 \leq \chi_g(T) \leq 4$ であることが示せました。
上の戦略は森でも通用するので、森のゲーム彩色数も4以下です。

では、3色と4色の区別はどうつければ良いのでしょうか？
これは難題で、現時点では効率的な判定方法が見つかっていない問題になります。
例えば最大次数で判定しようとすると、最大次数が3の94頂点のグラフであってゲーム彩色数4のグラフが発見されています*4。
しかし、次数3の頂点が存在しない場合は効率的な彩色数判定方法が発見されており、次数のアプローチが悪いわけでもないという面白い事態になっています。

さいごに

今回の内容は、[1410.5223] The game chromatic number of trees and forestsの一部を紹介したものになります。
ゲーム彩色数はカクタスや平面グラフにおいても有限の上界が求まっており、こちらも非自明な戦略からなる証明がゲーム問題ならではの面白さがあって一読の価値があります。
彩色数は四色問題ばかりが有名で、それ以外の彩色数については名前が知られていないことも多いのですが、実際に調べてみると面白い問題が数多くあります。
例えば平面ではなくその他の曲面に対する彩色数の上界とか、各国が二つの離れた領土を持つときの地図塗り問題とか、頂点と辺を同時に彩色してみるとか……。
これらの問題も難しいものは多いのですが、グラフのクラスを制限した時の性質がとても良いものも多く、またパズル的な解き方が多いので頭の体操としても面白い問題ばかりです。
また、今回紹介したゲーム彩色数も非自明なものが多く、考えてみるだけでも楽しい予想が沢山あります。

そこで、最後にゲーム彩色数に対する予想を一つ紹介します。良ければ解いてみてください。

予想: $k-$ 頂点彩色ゲームでAliceが勝利するならば、 $(k+1)-$ 頂点彩色ゲームでもAliceが勝利する。

*1:頂点彩色ゲームでAliceが勝った時の盤面は頂点彩色そのものです

*2:Aliceは常に各頂点を{0}+隣接頂点のmexで彩色することができ、これは最大次数+1で抑えられます

*3:余談: 最初は超立方体を用いて示そうとしたけど、Open Problemだった……

*4:ちなみに、最大次数4だと頂点数12のキャタピラグラフ $C(2, 2, 2, 2)$ が存在し、これが最小のゲーム彩色数4のグラフであることが示せます