Originator: Jarek Grytczuk (presented by Hong Liu - REGS 2011)
Definitions: A repetition in a list $S$ is a sublist of consecutive terms of $S$ composed of two identical blocks. A coloring of graph $G$ is nonrepetitive if the list of colors along any path in $G$ has no repetition. Note that every nonrepetitive coloring is a proper coloring. The nonrepetitive chromatic number of $G$, denoted $\pi(G)$, is the minimum number of colors in a nonrepetitive coloring of $G$. The nonrepetitive list coloring number or Thue choice number is the minimum $k$ such that whenever every vertex is given a list of at least $k$ colors, a nonrepetitive coloring can be chosen from the lists.
Background: Grytczuk [G] has provided a survey of results on nonrepetitive coloring of graphs. Recently, the list coloring version has been studied [GPZ]. He has mentioned a natural game version of the problem in seminars in Poland.
Given a graph $G$, two players take turns coloring vertices in $G$. Neither can create a repetition. Given a set of colors, the first player wants to finish coloring $G$, while the second player wants to color the vertices in such a way that a nonrepetitive coloring cannot be completed. The smallest size of a set of colors such that the first player has a winning strategy is the game nonrepetitive chromatic number of $G$, denoted $\pi_g(G)$. Always $\pi_g(G)\ge \pi(G)$. Note that $\pi_g(G)$ is to $\pi(G)$ as game chromatic number is to chromatic number.
Problems: Can $\pi_g(G)$ be bounded by a function of $\pi(G)$? When are they equal? Is $\pi_g(G)$ bounded on planar graphs or in terms of other graph parameters?
References:
[G] J.Grytczuk, Nonrepetitive colorings of graphs--A survey, Int J Math
Math Sci (2007), Art ID 74639, 10.
[GPZ] J.Grytczuk, J.Przybyło, and X.Zhu, Nonrepetitive list colorings of
paths, Random Structures Algorithms, DOI: 10.1002/rsa.20347.