7K-04
ゲーム彩色数が3以下である木についての考察
○岩井優斗,山田敏規(埼玉大)
与えられたグラフに対してAlice(先行)とBob(後攻)が交互に1つの未彩色な頂点を選んで彩色を施すとする.ただし,選ばれた頂点がすでに彩色された頂点と隣接している場合,その色とは異なる色が与えられるとする.このとき,Bobがどのような戦略を取ったとしてもすべての頂点に色が与えられるような色数の最小値をグラフのゲーム彩色数と呼ぶ.木のゲーム彩色数は高々4であることが知られているが,高々3である木の特徴づけは知られていない.小文では,ゲーム彩色数が3以下であるための十分条件を与える.