2023/08/25 by Botler, Fábio, Lomenha, Wanderson, de Souza, João Pedro · 1 citation
#05C15 #05C38 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2308.13485
We say that a sequence a1 ⋯ a2t of integers is repetitive if ai = ai+t for every i∈\1,…,t\. A walk in a graph G is a sequence v1 ⋯ vr of vertices of G in which vivi+1∈ E(G) for every i∈\1,…,r-1\. Given a k-coloring c\colon V(G)→\1,…,k\ of V(G), we say that c is walk-nonrepetitive (resp. stroll-nonrepetitive) if for every t∈ℕ and every walk v1⋯ v2t the sequence c(v1) ⋯ c(v2t) is not repetitive unless vi = vi+t for every i∈\1,…,t\ (resp. unless vi = vi+t for some i∈\1,…,t\). The walk (resp. stroll) chromatic number σ(G) (resp. ρ(G)) of G is the minimum k for which G has a walk-nonrepetitive (resp. stroll-nonrepetitive) k-coloring. Let Cn and Pn denote, respectively, the cycle and the path with n vertices. In this paper we present three results that answer questions posed by Barát and Wood in 2008: (i) σ(Cn) = 4 whenever n≥ 4 and n ∉\5,7\; (ii) ρ(Pn) = 3 if 3≤ n≤ 21 and ρ(Pn) = 4 otherwise; and (iii) ρ(Cn) = 4, whenever n ∉\3,4,6,8\, and ρ(Cn) = 3 otherwise. In particular, (ii) improves bounds on n obtained by Tao in 2023.