Coloring complexity of graphs Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ for this vertex. The game ends when a monochromatic edge is discovered. Let $X(G)$ be the maximal length of the game under optimal play by both players (Alice wants to shorten the game as possible, Bob wants to delay it as possible). For example, $X(K_n) = n$ and $X(C_{2n+1}) = \Theta(\log n)$.

Is this game known?
It looks fairly similar to 


  Coloring random graphs online without creating monochromatic subgraphs (Reto Spöhel, Torsten Mütze, and Thomas Rast)
  Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), PR 137, 145-158.



SODA PDF
Journal version
Conference proceedings