New lower bounds on the non-repetitive chromatic number of some graphs

A graph $G$ is said to be (vertex) non-repetitively colored if no simple path in $G$ has a sequence of vertex colors that forms a repetition. Formally, a coloring $c:V(G)\to \{1,2,\dots ,k\}$ is non-repetitive if, for every path $⟨v_1,v_2,\dots ,v_{2m}⟩$ in $G$, the sequence of colors $c(v_1),c(v_2),\dots ,c(v_{2m})$ is not of the form $ww$, where $w$ is a sequence of $m$ colors. The minimum number of colors required for such a coloring is called the \emph{non-repetitive chromatic number} of $G$, denoted by $\pi (G)$. In this paper, we primarily prove that $\pi (P\mathrm{\square }P)\ge 6$ and $\pi (P⊠P)\ge 9$, where $P\mathrm{\square }P$ and $P⊠P$ are the Cartesian product and the strong product of two infinite paths, respectively. This improves upon the previous best lower bounds.