论文标题
永恒的游戏色数随机图
The Eternal Game Chromatic Number of Random Graphs
论文作者
论文摘要
Klostermeyer和Mendoza最近引入的Eternal Graph着色问题是图形游戏的一个版本，其中两个玩家轮流适当地着色。在本说明中，我们研究了永恒的游戏色素随机图。我们表明，概率$χ_{g}^{\ infty}（g_ {n，p}）=（\ frac {p} {2} {2} + o（1））n $ for Odd $ n $，以及$ n $，甚至对于$ p = \ frac {1} {k k} $ for $ k n $ for Some $ kbb for Some $ k b。上限甚至适用于$ n $，也适用于$ p $的任何其他值，但是在这种情况下，我们的上限并不锋利。最后，我们回答了Klostermeyer和Mendoza提出的一个问题。
The eternal graph colouring problem, recently introduced by Klostermeyer and Mendoza, is a version of the graph colouring game, where two players take turns properly colouring a graph. In this note, we study the eternal game chromatic number of random graphs. We show that with high probability $χ_{g}^{\infty}(G_{n,p}) = (\frac{p}{2} + o(1))n$ for odd $n$, and also for even $n$ when $p=\frac{1}{k}$ for some $k \in \mathbb{N}$. The upper bound applies for even $n$ and any other value of $p$ as well, but we conjecture in this case this upper bound is not sharp. Finally, we answer a question posed by Klostermeyer and Mendoza.
