2022/05/23 by Miller, Joe, Warnberg, Nathan
#05C15 (Primary) #05C38 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2205.11621
A k-term arithmetic progression (k-AP) in a graph G is a list of vertices such that each consecutive pair of vertices is the same distance apart. If c is a coloring function of the vertices of G and a k-AP in G has each vertex colored distinctly, then that k-AP is a rainbow k-AP. The anti-van der Waerden number of a graph G with respect to k is the least positive integer r such that every surjective coloring with domain V(G) and codomain \1,2,…,r\ = [r] is guaranteed to have a rainbow k-AP. This paper focuses on 3-APs and graph products with cycles. Specifically, the anti-van der Waerden number with respect to 3 is determined precisely for Pm \square Cn, Cm\square Cn and G\square C2n+1.