The Eternal Game Chromatic Number of Random Graphs

Abstract

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 ${\chi }_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.

16 pages