2023/03/28 by Tianyi Tao, Tao, Tianyi · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2303.16237
openalex publication_date 2023/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, a vertex coloring f is called nonrepetitive if for all k∈\mathbb N and all P2k=⟨ v1, ⋯, vk,vk+1, ⋯, v2k⟩ (path of 2k vertices) in G, there must be some 1≤ i≤ k such that f(vi)\not=f(vk+i). We use π(G) to denote the minimum number of colors required for G to be nonrepetitively colored. In 1906, Thue proved that π(Pn)≤3 for all n. In this paper, we focus on grids, which are the Cartesian products of paths. We prove that 5≤π(Pn\square Pn)≤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.