2025/10/13 by Tao, Tianyi, Zhang, Junchi, Zhang, Wentao +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.11263
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) → \1, 2, …, k\ \) is non-repetitive if, for every path \(⟨ v1, v2, …, v2m ⟩\) in \( G \), the sequence of colors \( c(v1), c(v2), …, c(v2m) \) 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 non-repetitive chromatic number of \(G\), denoted by \(π(G)\). In this paper, we primarily prove that \(π(P \square P) ≥ 6\) and \(π(P \boxtimes P) ≥ 9\), where \( P \square P \) and \( P \boxtimes P \) are the Cartesian product and the strong product of two infinite paths, respectively. This improves upon the previous best lower bounds.