The nonrepetitive colorings of grids

Abstract

For a graph $G$, a vertex coloring $f$ is called nonrepetitive if for all $k\in \mathbb{N}$ and all $P_{2k}=⟨v_1,\cdots ,v_k,v_{k+1},\cdots ,v_{2k}⟩$ (path of $2k$ vertices) in $G$, there must be some $1\le i\le k$ such that $f(v_i)\ne f(v_{k+i})$. We use $\pi (G)$ to denote the minimum number of colors required for $G$ to be nonrepetitively colored. In 1906, Thue proved that $\pi (P_n)\le 3$ for all $n$. In this paper, we focus on grids, which are the Cartesian products of paths. We prove that $5\le \pi (P_n\square P_n)\le 12$ for sufficiently large $n$, where the previous best lower bound was 4 and upper bound was 16. Moreover, we also discuss nonrepetitive coloring of the Cartesian product of complete graphs.

15 pages, 14 figures